归并排序（merge sort）是一种采用了分治思想的排序算法
- 划分divide：将输入数列划分为左右两部分
- 递归的分别对该左右两部分进行排序
- 合并已经排序好的左右两部分数列为最终结果
void merge_sort(一个数组) {
if (可以很容易处理) return;
merge_sort(左半个数组);
merge_sort(右半个数组);
merge(左半个数组, 右半个数组);
}C++ STL
template<class Iter>
void merge_sort(Iter first, Iter last)
{
if (last - first > 1) {
Iter middle = first + (last - first) / 2;
merge_sort(first, middle);
merge_sort(middle, last);
std::inplace_merge(first, middle, last);
}
}例子 327. 区间和的个数
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
利用归并排序分治的思想，将前缀和数列分块，分别求出分块子数列满足条件的区间和的个数。然后再计算出满足条件的区间跨越前述分块数列的个数（合并过程）。**由于前述分块数列已是有序数列，可以很容易计算跨分块满足条件子区间的个数。**其中计算区间和个数和合并有序数组采用了lambda函数的形式是为了使计算步骤更清楚。
主要计算代码为
function<int(int, int)> merge_sort = [&](int l, int r)->int{
if(l == r) return 0;
auto mid = (l + r) >> 1;
auto nl = merge_sort(l, mid);
auto nr = merge_sort(mid + 1, r);
// merge count
auto ans = nl + nr + count(l, r);
merge(l, r);
return ans;
};C++ 完整代码
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
vector<long long> preSum{0};
for(auto& i : nums) preSum.push_back(preSum.back()+i);
vector<long long> t(preSum.size());
auto count = [&preSum, lower, upper](int l, int r){
int ans = 0;
auto mid = (l + r)>>1;
auto now = l;
auto lnow = mid + 1;
auto rnow = mid + 1;
while(now <= mid){
while(lnow <= r && preSum[lnow] - preSum[now] < lower) lnow++;
while(rnow <= r && preSum[rnow] - preSum[now] <= upper) rnow++;
ans += rnow - lnow;
now++;
}
return ans;
};
auto merge = [&t, &preSum](int l, int r){
auto mid = (l + r)>>1;
auto p = l, q = mid+1, s = l;
while (s <= r) {
if (p >= mid+1 || (q <= r && preSum[p] > preSum[q]))
t[s++] = preSum[q++];
else
t[s++] = preSum[p++];
}
for(auto i = l; i <= r; ++i)
preSum[i] = t[i];
};
function<int(int, int)> merge_sort = [&](int l, int r)->int{
if(l >= r) return 0;
auto mid = (l + r) >> 1;
auto nl = merge_sort(l, mid);
auto nr = merge_sort(mid + 1, r);
auto ans = nl + nr + count(l, r);
merge(l, r);
return ans;
};
return merge_sort(0, nums.size());
}
};评论 (0)
