归并排序实战：计算右侧小于当前元素个数与翻转对

算法流程解析

50. 翻转对

493. 翻转对 - 力扣（LeetCode）

题目描述

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

题目示例

输入: [1, 3, 2, 3, 1] 输出: 2 解释: 翻转对有 (1, 3), (3, 2)。注意 (3, 2) 是因为 3 > 2*2 不成立，这里应该是 (3, 1) 和 (3, 1) 等组合，具体看数值关系。

题目解析

翻转对和逆序对的定义大同小异。逆序对是前面的数大于后面的数，而翻转对要求前面的数大于后面某个数的两倍。

既然涉及区间统计，依旧可以用归并排序的思想来解决。我们将问题拆解为三部分：左半区间翻转对的数量，右半区间翻转对的数量，以及跨越左右两区间的翻转对数量。

解题思路

大思路与求逆序对一致，区别在于统计条件更苛刻。上一道题我们可以一边合并一遍计算，因为只要 left > right 就能确定逆序关系。

但这道题要求 left > 2 * right。如果我们直接混着合并，一旦开始交换元素，原本满足条件的配对可能就被破坏了，或者无法快速定位。因此，必须在归并排序之前完成翻转对的统计，或者说，先统计再合并，把这两个动作分开。

C++ 实现

class Solution {
public:
    vector<int> tmp;
    int count = 0;

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        tmp.resize(n);
        mergesort(nums, 0, n - 1);
        return count;
    }

    void mergesort(vector<int>& nums, int left, int right) {
        if(left >= right) return;
        
        int mid = (right - left) / 2 + left;
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);
        
        // 关键点：先统计，再合并
        // 此时左右区间已经分别有序
        int cur1 = left, cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right) {
            // 当左边大于右边的两倍才会进行求值
            if((long long)nums[cur1] > 2LL * nums[cur2]) {
                count += right - cur2 + 1;
                cur1++;
            } else {
                cur2++;
            }
        }
        
        // 统计完后，再进行标准的归并操作
        cur1 = left;
        cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] > nums[cur2]) {
                tmp[i++] = nums[cur1++];
            } else {
                tmp[i++] = nums[cur2++];
            }
        }
        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];
        }
    }
};

算法流程解析