493. 翻转对

Problem: 493. 翻转对

文章目录

• 思路
• 解题方法
• 复杂度
• Code

思路

这个问题可以使用归并排序的思想来解决。在归并排序的过程中，我们可以统计翻转对的数量。具体来说，对于数组的任意两个子数组，如果左边的子数组的最大值大于右边子数组的最小值的两倍，那么左边子数组中所有大于右边子数组最小值的两倍的元素都可以与右边子数组形成翻转对。

解题方法

我们使用递归的方式，将数组分为左右两部分，然后分别对左右两部分进行排序和统计翻转对的数量。在合并两个已排序的子数组以统计翻转对的数量时，我们可以使用双指针的方法，左指针指向左子数组的开始，右指针指向右子数组的开始，如果左指针指向的元素大于右指针指向的元素的两倍，那么左指针右边的所有元素都可以与右指针形成翻转对，然后右指针向右移动一位，否则，左指针向右移动一位。这样，我们就可以在合并的过程中统计翻转对的数量。

复杂度

时间复杂度:

O ( n log ⁡ n ) O(n \log n) O(nlogn)，其中 n 是数组的长度。我们需要对数组进行归并排序，时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn)。

空间复杂度:

O ( n ) O(n) O(n)，我们需要额外的空间来存储归并过程中的临时数组。

Code

class Solution {
    public static int MAXN = 50001;
    public static int[] help = new int[MAXN];

    public static int reversePairs(int[] nums) {
        return counts(nums, 0, nums.length - 1);
    }

    private static int counts(int[] nums, int l, int r) {
        if (l == r) {
            return 0;
        }
        int m = (l + r) / 2;
        return counts(nums, l, m) + counts(nums,m + 1, r) + merge(nums, l, m, r);
    }

    private static int merge(int[] arr, int l, int m, int r) {
        int ans = 0;
        for(int i = l, j = m + 1; i <= m; i++) {
            while(j <= r && arr[i] > 2 * (long)arr[j]) {
                j++;
            }
            ans += j - m - 1;
        }
        // 正常merge
        int i = l;
        int a = l;
        int b = m + 1;
        while (a <= m && b <= r) {
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= m) {
            help[i++] = arr[a++];
        }
        while (b <= r) {
            help[i++] = arr[b++];
        }

        for(i = l; i <= r; i++) {
            arr[i] = help[i]; 
        }
        return ans;

    }
}