题目描述:
给定一个数组 nums
,如果 i < j
且 nums[i] > 2*nums[j]
我们就将 (i, j)
称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1] 输出: 2
示例 2:
输入: [2,4,3,5,1] 输出: 3
注意:
- 给定数组的长度不会超过
50000
。 - 输入数组中的所有数字都在32位整数的表示范围内。
题目链接:
. - 力扣(LeetCode)
题目主要思路:
其实就是利用归并分治的思想,但是跟 “LCR170. 交易中的逆序队” 以及 "315. 计算右侧小于当前元素的个数" 这两道题目的结构不太一样。为什么?因为上述两道题,可以借助归并的时候顺便计算结构,即我们在判断nums[cur1] 和 nums[cur2]的时候可以顺便计算结果,而这道题的结果条件是nums[i] > 2*nums[j]。
这道题如果我们在判断nums[cur1] 和 nums[cur2]的时候顺便计算结果,很容易漏结果并且复杂些许。那为什么说利用归并分治的思想呢?因为我们可以在归并前计算结果。
解题代码:
class Solution {
public:int tmp[50010] = {0};int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size()-1);}int mergeSort(vector<int>& nums, int left, int right){if (left >= right) return 0;int mid = (left + right) >> 1;int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid+1, right);int cur1 = left, cur2 = mid+1, i = 0;// 先计算结果while (cur1 <= mid) {while (cur2 <= right && nums[cur1]/2.0 <=nums[cur2]) ++cur2;if (cur2 > right) break;ret += right - cur2 + 1;++cur1;}cur1 = left, cur2 = mid+1;while (cur1 <= mid && cur2 <= right){ // 排降序 if (nums[cur1] < nums[cur2]) {tmp[i++] = nums[cur2++];}else {tmp[i++] = nums[cur1++];}}while (cur1 <= mid) {tmp[i++] = nums[cur1++];}while (cur2 <= right) {tmp[i++] = nums[cur2++];}// 将排序完的数据写入原数组for (int i = left; i <= right; ++i) {nums[i] = tmp[i-left];}return ret;}
};