[LeetCode] 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位整数的表示范围内。

题目链接：

. - 力扣（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;
    }
};

原文地址：https://blog.csdn.net/weixin_65043441/article/details/142787466

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！