示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
题解思路
这题结合示例一眼看去觉得太简单了 直接暴力二重循环 结果自然是超时.. 要不这题难度也不会是 困难
实际上是利用归并排序的性质 推荐直接看官方题解视频的思路
class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<int> temp(nums.size());
return mergeSort(nums, 0, nums.size() - 1, temp);
}
private:
int mergeSort(vector<int>& nums, int begin, int end, vector<int>& temp) {
if (begin < end) {
int mid = (begin + end)/2;
int ret = mergeSort(nums, begin, mid, temp) + mergeSort(nums, mid + 1, end, temp);
int i = begin;
int j = mid + 1;
for (int k = 0; k <= end - begin; k++) {
if (i <= mid && (j > end || nums[i] <= nums[j])) {
temp[k] = nums[i++];
ret += (j - mid - 1);
} else {
temp[k] = nums[j++];
}
}
memcpy(&nums[begin], &temp[0], (end - begin + 1) * sizeof(int));
return ret;
}
return 0;
}
};