問題描述
給定一個數(shù)組 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我們就將 (i, j) 稱作一個重要翻轉(zhuǎn)對。
你需要返回給定數(shù)組中的重要翻轉(zhuǎn)對的數(shù)量。
Example
示例 1:
輸入: [1,3,2,3,1]
輸出: 2
示例 2:
輸入: [2,4,3,5,1]
輸出: 3
題目鏈接: 493. 翻轉(zhuǎn)對(難度：困難)
思路
這道題可以采用歸并排序 + 二分查找來解決。我們可以先考慮一個最簡單的情況，如 [-10, -6]，我們可以先將 [-10, -10] 分割為 L 和 R 兩個子數(shù)組，其中 L = [-10], R = [-6]。顯然，L 和 R 中都只有一個元素，本身就是有序數(shù)組，同時翻轉(zhuǎn)對數(shù)為0。將 L 和 R 合并排序，由于 L[0] > 2 * R[0], 得到排序后的數(shù)組為 [-10, -6], 且翻轉(zhuǎn)對數(shù)為 1。
上述過程大體上描繪了代碼主體的框架，要求出一個數(shù)組的翻轉(zhuǎn)對數(shù)，我們需要將其劃分為 L 和 R，并求出 L 和 R 中的翻轉(zhuǎn)對數(shù) v1 和 v2，然后對排好序的 L 和 R 進(jìn)行合并排序，得到翻轉(zhuǎn)對數(shù) v3，則數(shù)組本身的翻轉(zhuǎn)對數(shù)就是 v1 + v2 + v3。
這道題有兩個值得注意的細(xì)節(jié)：
- 在對 L 和 R 進(jìn)行合并排序的過程中，由于 L 和 R 都是有序數(shù)組，因此可以使用二分查找來優(yōu)化
- 由于可能存在負(fù)數(shù)，因此可能會出現(xiàn) L[i] < R[j], 但 L[i] > 2 * R[j] 的情況，對于這種情況，需要從頭掃描整個數(shù)組，因為 L[i] 前面的元素也可能大于 2 * R[j]。若為正數(shù)，則直接掃描 L[i, end) 即可，因為L[i] 前面的元素小于 L[i]，而 L[i] < 2 * R[j]， 所以 L[i] 前面的元素也都不需要考慮了
代碼
class Solution {
public:
using ull = unsigned long long;
static const int MAX = 50000;
long long L[MAX / 2 + 2] = {0}, R[MAX / 2 + 2] = {0};
ull Merge(vector<int>& nums, int left, int mid, int right){
int L_end = mid - left;
int R_end = right - mid;
for(int i = 0;i < L_end;++i)
L[i] = nums[left + i];
for(int i = 0;i < R_end;++i)
R[i] = nums[mid + i];
L[L_end] = static_cast<long long>(numeric_limits<int>::max()) + 2;
R[R_end] = static_cast<long long>(numeric_limits<int>::max()) + 2;
ull cnt = 0;
int i = 0, j = 0;
for(int k = left;k < right;++k){
if(L[i] < R[j]){
nums[k] = L[i++];
}else{
if(R[j] < 0)
cnt += L_end - (upper_bound(L, L + L_end, R[j] * 2) - L);
else
cnt += L_end - (upper_bound(L + i, L + L_end, R[j] * 2) - L);
nums[k] = R[j++];
}
}
return cnt;
}
int MergeSort(vector<int>& nums, int left, int right){
ull v1 = 0, v2 = 0, v3 = 0;
if(left + 1 < right){
int mid = (left + right) >> 1;
v1 = MergeSort(nums, left, mid);
v2 = MergeSort(nums, mid, right);
v3 = Merge(nums, left, mid, right);
}
return v1 + v2 + v3;
}
int reversePairs(vector<int>& nums) {
return MergeSort(nums, 0, nums.size());
}
};
運行結(jié)果：456ms, 42 MB
