翻转对

描述

给定一个数组 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）
链接：https://leetcode.cn/problems/reverse-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这个问题的解决方法是使用归并排序。我们可以将数组分成两半，然后递归地对每个子数组进行归并排序。在归并过程中，我们可以计算逆序对的数量。

假设我们有两个已排序的子数组A和B，我们需要将它们合并成一个已排序的数组C。我们可以使用两个指针i和j来分别追踪A和B中的元素。如果A[i] > 2*B[j]，那么我们可以知道从A[i]到A[mid]的所有元素都大于B[j]，其中mid是A的最后一个元素的索引。因此，我们可以将逆序对的数量增加mid-i+1。如果A[i] <= 2*B[j]，那么我们只需要将i向后移动一位。

在归并排序的过程中，我们还需要将两个子数组合并成一个已排序的数组。我们可以使用另外一个指针k来追踪新数组C中的元素。我们可以比较A[i]和B[j]，并将较小的元素放入C[k]中。然后，我们将指针i或j向后移动一位，并将指针k向后移动一位。

最后，我们将新数组C中的元素复制回原数组中，并返回逆序对的数量。

C++代码

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return mergeSort(nums, 0, nums.size() - 1);
    }

private:
    int mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right) + merge(nums, left, mid, right);
        return count;
    }

    int merge(vector<int>& nums, int left, int mid, int right) {
        int count = 0;
        vector<int> cache(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if ((long long)nums[i] > 2 * (long long)nums[j]) {
                count += mid - i + 1;
                ++j;
            } else {
                ++i;
            }
        }
        i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                cache[k++] = nums[i++];
            } else {
                cache[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            cache[k++] = nums[i++];
        }
        while (j <= right) {
            cache[k++] = nums[j++];
        }
        for (int p = 0; p < k; ++p) {
            nums[left + p] = cache[p];
        }
        return count;
    }
};