使用归并排序,在排序的过程中统计逆序对
C++ 代码
class Solution {
public:
int reversePairs(vector<int>& nums) {
return merge_sort(nums, 0, nums.size()-1);
}
int merge_sort(vector<int>& nums, int start, int end) {
// 边界条件
if(start >= end)return 0;
int mid = (start+end) >> 1;
int left = merge_sort(nums, start, mid);
int right = merge_sort(nums, mid+1, end);
int res = 0;
int i = start, j = mid+1;
while(i<=mid && j<=end) {
// 双指针统计
if( nums[i] > 2ll*nums[j] ) {
res += mid - i + 1;
j++;
} else {
i++;
}
}
// sort
vector<int> tmp;
tmp.reserve(end-start+1);
i = start, j = mid+1;
while(i<=mid && j<=end) {
if(nums[i] <= nums[j])tmp.push_back(nums[i++]);
else tmp.push_back(nums[j++]);
}
while(i<=mid)tmp.push_back(nums[i++]);
while(j<=end)tmp.push_back(nums[j++]);
for(int k=start, l=0; k<=end; ++k) {
nums[k] = tmp[l++];
}
res += left + right;
return res;
}
};