每日OJ题_分治归并④_力扣493. 翻转对

目录

力扣493. 翻转对

解析代码

---

力扣493. 翻转对

493. 翻转对

难度 困难

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

1. 给定数组的长度不会超过50000。
2. 输入数组中的所有数字都在32位整数的表示范围内。

class Solution {
public:
    int reversePairs(vector<int>& nums) {
 
    }
};

---

解析代码

        大思路与求逆序对的思路一样，就是利用归并排序的思想，将求整个数组的翻转对的数量，转换成三部分：

• 左半区间翻转对的数量。
• 右半区间翻转对的数量。
• 一左一右选择时翻转对的数量。

        重点就是在合并区间过程中，如何计算出翻转对的数量。 与上个问题不同的是，上一道题我们可以一边合并一遍计算，但是这道题要求的是左边元素大于右边元素的两倍，如果我们直接合并的话，是无法快速计算出翻转对的数量的。

        例如 left = [4, 5, 6] right = [3, 4, 5] 时，如果是归并排序的话，需要计算 left 数组中有多少个 能与 3 组成翻转对。但是我们要遍历到最后一个元素 6 才能确定，时间复杂度较高。 因此需要在归并排序之前完成翻转对的统计。因为左右区间是有序的，所以使用双指针统计。

这里用升序（也可以用降序）：

class Solution {
    vector<int> tmp;
public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return mergeSortCnt(nums, 0, nums.size() - 1);
    }
 
    int mergeSortCnt(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return 0;
        int ret = 0, mid = (left + right) >> 1;
        // 先计算左右两侧翻转对数量
        ret += mergeSortCnt(nums, left, mid);
        ret += mergeSortCnt(nums, mid + 1, right);
 
        // 计算翻转对数量
        int cur1 = left, cur2 = mid + 1, i = left;
        while(cur2 <= right) // 升序的情况
        {
            while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0)
            {
                cur1++;
            }
            if(cur1 > mid)
                break;
            ret += mid - cur1 + 1;
            cur2++;
        }
 
        // 合并两个有序数组
        cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        
		while (cur1 <= mid) 
            tmp[i++] = nums[cur1++];
		while (cur2 <= right) 
            tmp[i++] = nums[cur2++];
		for (int j = left; j <= right; j++)
			nums[j] = tmp[j];
        
        return ret;
    }
};