思路
简要来说，归并分治的思路就是，在归并排序的基础上，统计答案。
具体而言，可以从以下步骤进行考虑：
- 答案是否可以从左区间、右区间和左跨右区间得到。
- 排序是否对寻找答案有利。
例题分析
翻转对
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
依题意，实际为找满足nums[左] > 2*nums[右]的个数。
考虑暴力方法，对于每个坐标，依次向右遍历，寻找是否满足nums[i] > 2*nums[j]的坐标，同时进行计数。显然，暴力解的时间复杂度是O(n^2)的。
尝试使用归并分治的思想进行求解，注意到，如果取中点mid，答案可以从左区间、右区间和左跨右区间得到。接下来，考虑第二点，排序是否对寻找答案有利？对于两个已经排好序的数组而言，可以分别看成左边元素的集合和右边元素的集合，对于单个集合中的元素而言，此时坐标顺序已不重要，因为在下游的递归中，我们已经得到了那部分的结果。此时，我们可以使用滑动窗口的思想，即一次遍历，寻找答案。设定两个指针，i和j，分别在左部分和右部分中迭代，满足条件nums[左] > 2*nums[右]时，j向右边遍历，直到越界。因为对于左部分，顺序是按从小到大排序的，即是说，*左部分[l, mid]的元素如果在右部分[mid+1, r]*有三个元素满足，对于左部分的下一个元素而言，它至少有三个元素满足。由此，我们可以用如下代码，统计答案。
1
2
3
4
5
6
7
| int ans = 0;
for (int i = l, j = mid+1; i <= mid; ++i) {
while (j <= r && 1LL * nums[i] > 1LL * nums[j] << 1) {
j++;
}
ans += j - mid - 1;
}
|
这道题的整体代码则如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public:
int help[50000] = {0};
int merge(vector<int>& nums, int l, int mid, int r) {
int ans = 0;
for (int i = l, j = mid+1; i <= mid; ++i) {
while (j <= r && 1LL * nums[i] > 1LL * nums[j] << 1) {
j++;
}
ans += j - mid - 1;
}
int i = l, a = l, b = mid + 1;
while (a <= mid && b <= r) {
help[i++] = nums[a] <= nums[b] ? nums[a++] : nums[b++];
}
while (a <= mid) {
help[i++] = nums[a++];
}
while (b <= r) {
help[i++] = nums[b++];
}
for (int j = l; j <= r; ++j) {
nums[j] = help[j];
}
return ans;
}
int mergeSort(vector<int>& nums, int l, int r) {
if (l == r) {
return 0;
}
int mid = l + (r - l) / 2;
return mergeSort(nums, l, mid) + mergeSort(nums, mid+1, r) + merge(nums, l, mid, r);
}
int reversePairs(vector<int>& nums) {
int n = nums.size();
return mergeSort(nums, 0, n-1);
}
};
|
时间复杂度
一般情况下，归并分治的时间复杂度和归并排序一致，为O(n*log n)