翻转对

发表于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，493. Reverse Pairs

先看题目描述

DsvLhq.png

大意就是给定一个数组 nums，让我们找出其中所有的翻转对，翻转对的定义是 (i, j) 满足 i < j 且 nums[i] > 2 * nums[j]

算法和思路

分治法

这题我们可以使用归并排序来解决，在归并排序的过程中，假设对于数组 nums[l…r] 而言，我们已分别求出了子数组 nums[l…m] 与 nums[m + 1…r] 的翻转对数目，并已将两个子数组分别排好序，则 nums[l…r] 中的翻转对数目，就等于两个子数组的翻转对数目之和，再加上左右端点分别位于两个子数组的翻转对的数目

我们可以为两个数组分别维护指针 i 和 j，初始化 i 为 l，j 为 m + 1，对于任意给定的 i 而言，我们不断地向右移动 j，直至 nums[i] <= 2 * nums[j]。此时，意味着以 i 为左端点的翻转对数量为 j - (m + 1)。随后，我们再将 i 向右移动一个单位，并用相同的方式计算以当前 i 为左端点的翻转对数量，不断重复这样的过程，就能够求出所有左右端点分别位于两个子数组的翻转对的数目

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int reversePairs(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        return reversePairsRecursive(nums, 0, len - 1, temp);
    }

    private int reversePairsRecursive(int[] nums, int left, int right, int[] temp) {
        int len = right - left + 1;
        if (len <= 1) return 0;
        int mid = left + (right - left) / 2;
        int n1 = reversePairsRecursive(nums, left, mid, temp);
        int n2 = reversePairsRecursive(nums, mid + 1, right, temp);
        int res = n1 + n2;
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long)nums[i] > (long)nums[j] * 2) {
                j++;
            }
            res += j - (mid + 1);
        }
        System.arraycopy(nums, left, temp, left, len);
        int m = left;
        int n = mid + 1;
        for (int index = left; index <= right; index++) {
            if (m > mid) {
                nums[index] = temp[n++];
            } else if (n > right) {
                nums[index] = temp[m++];
            } else {
                if (temp[m] <= temp[n]) {
                    nums[index] = temp[m++];
                } else {
                    nums[index] = temp[n++];
                }
            }
        }
        return res;
    }
}

注意：reversePairsRecursive() 函数中的 int j = mid + 1 语句不能放在 for 循环内部，应该放在外部，否则的话这个 for 循环的时间复杂度将达到 O(n^2^)，而不是原本的 O(n)，这样将导致代码运行超出时间限制。因为 nums[left..mid] 和 nums[mid + 1…right] 部分均已按升序排列，所以对于所有满足 nums[i] > 2 * nums[j] 的 j，均有 nums[i + 1] > 2 * nums[j]，那么 j 指针不需要有回溯操作，只需要向右移动即可，j 指针的定义应放在 for 循环外部