327. Count of Range Sum(inplace_marge)
Given an integer array nums
, return the number of range sums that lie in [lower, upper]
inclusive.
Range sum S(i, j)
is defined as the sum of the elements in nums
between indices i
and j
(i
≤ j
), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Input: nums = [2, 5, -1], lower = -2, upper = 2, Output: 3 Explanation: The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.
Approach #1: C++.
class Solution { public: int countRangeSum(vector<int>& nums, int lower, int upper) { int len = nums.size(); if (len == 0) return 0; vector<long> sum(len+1, 0); for (int i = 0; i < len; ++i) sum[i+1] += sum[i] + nums[i]; return mergeSort(sum, lower, upper, 0, len+1); } private: int mergeSort(vector<long>& sum, int lower, int upper, int left, int right) { if (right - left <= 1) return 0; int mid = left + (right - left) / 2; int m = mid, n = mid, count = 0; count = mergeSort(sum, lower, upper, left, mid) + mergeSort(sum, lower, upper, mid, right); for (int i = left; i < mid; ++i) { while (m < right && sum[m] - sum[i] < lower) m++; while (n < right && sum[n] - sum[i] <= upper) n++; count += n - m; } inplace_merge(sum.begin()+left, sum.begin()+mid, sum.begin()+right); return count; } };
Approach #2: Java.
class Solution { public int countRangeSum(int[] nums, int lower, int upper) { if (nums == null || nums.length == 0) return 0; long[] sums = new long[nums.length]; long sum = 0; for (int i = 0; i < nums.length; ++i) { sum += nums[i]; sums[i] += sum; } return mergeSort(sums, lower, upper, 0, nums.length-1); } private int mergeSort(long[] sums, int lower, int upper, int left, int right) { if (right < left) return 0; else if (left == right) { if (sums[left] >= lower && sums[right] <= upper) return 1; else return 0; } int mid = left + (right - left) / 2; int count = mergeSort(sums, lower, upper, left, mid) + mergeSort(sums, lower, upper, mid+1, right); int m = mid+1, n = mid+1; for (int i = left; i <= mid; ++i) { while (m <= right && sums[m] - sums[i] < lower) m++; while (n <= right && sums[n] - sums[i] <= upper) n++; count += n - m; } mergeHelper(sums, left, mid, right); return count; } private void mergeHelper(long[] sums, int left, int mid, int right) { int i = left; int j = mid + 1; long[] copy = new long[right-left+1]; int p = 0; while (i <= mid && j <= right) { if (sums[i] < sums[j]) { copy[p++] = sums[i++]; } else { copy[p++] = sums[j++]; } } while (i <= mid) { copy[p++] = sums[i++]; } while (j <= right) { copy[p++] = sums[j++]; } System.arraycopy(copy, 0, sums, left, right-left+1); } }
Approach #3: Python.
class Solution(object): def countRangeSum(self, nums, lower, upper): """ :type nums: List[int] :type lower: int :type upper: int :rtype: int """ first = [0] for num in nums: first.append(first[-1] + num) def sort(lo, hi): mid = (lo + hi) / 2 if mid == lo: return 0 count = sort(lo, mid) + sort(mid, hi) i = j = mid for left in first[lo:mid]: while i < hi and first[i] - left < lower: i += 1 while j < hi and first[j] - left <= upper: j += 1 count += j - i first[lo:hi] = sorted(first[lo:hi]) return count return sort(0, len(first))
Notes:
C++ -----> inplace_merge
default (1) |
template <class BidirectionalIterator> void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); |
---|---|
custom (2) |
template <class BidirectionalIterator, class Compare> void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); |
Merges two consecutive sorted ranges: [first,middle)
and [middle,last)
, putting the result into the combined sorted range [first,last)
.
The elements are compared using operator<
for the first version, and comp for the second. The elements in both ranges shall already be ordered according to this same criterion (operator<
or comp). The resulting range is also sorted according to this.
The function preserves the relative order of elements with equivalent values, with the elements in the first range preceding those equivalent in the second.
for example:
// inplace_merge example #include <iostream> // std::cout #include <algorithm> // std::inplace_merge, std::sort, std::copy #include <vector> // std::vector int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; std::vector<int> v(10); std::vector<int>::iterator it; std::sort (first,first+5); std::sort (second,second+5); it=std::copy (first, first+5, v.begin()); std::copy (second,second+5,it); std::inplace_merge (v.begin(),v.begin()+5,v.end()); std::cout << "The resulting vector contains:"; for (it=v.begin(); it!=v.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; }
output:
The resulting vector contains: 5 10 10 15 20 20 25 30 40 50
相关文章
- PHP超过三十秒怎么办Maximum execution time of 30 seconds exceeded
- hdu 1811Rank of Tetris (并查集 + 拓扑排序)
- [Angular2 Form] Nested formGroup, and usage of formGroupName
- Too many levels of symbolic links 问题
- [Typescript] Prevent Type Widening of Object Literals with TypeScript's const Assertions
- [Algorithm] Largest sum of non-adjacent numbers
- Concept of Key in Data Warehouse
- Why all application lack a kind of most really charm ?
- test of ui5 duplicate control id
- 成功解决TabError: inconsistent use of tabs and spaces in indentation
- leetcode 697. Degree of an Array
- leetcode 371. Sum of Two Integers
- C++堆内存错误:CRT detected that the application wrote to memory after end of heap buffer