力扣 剑指 Offer 51. 数组中的逆序对

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

题目来源：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

大致题意：
给定一个数组，求出数组中逆序对的个数，逆序对的定义为：

• 设有 i < j，若 nums[i] > nums[j] 则 nums[i] 与 nums[j] 构成逆序对

思路

若有两个升序数组 nums1 和 nums2，那么如何比较这两个升序数组合并后的逆序对个数？

1. 首先，由于两个数组本身是升序数组，所以数组本身中不存在逆序对
2. 那么，这两个升序数组合并后的逆序对个数取决与前一个数组中有多少元素大于后一个数组

使用双指针 i 和 j 分别表示两个升序数组的遍历位置

若 nums1[i] 大于 nums2[j]，那么 i 至前一个数组末尾所有元素都大于 nums2[j]，这些元素都与 nums2[j] 构成逆序对，统计个数并后移指针 j；

若 nums1[i] 不大于 nums2[j]，那么指针 i 后移

通过上述方法可以统计两个升序数组的逆序对个数，那么若两个数组不是升序数组呢？

即若有两个数组 nums1 和 nums2，那么如何比较这两个数组合并后的逆序对个数？

1. 首先，统计 nums1 和 nums2 本身的逆序对个数，然后将两个数组排序
2. 按照上述方法计算两个升序数组合并后的逆序对个数

于是就可以使用归并排序的思路，在归并排序的同时计算逆序对个数

具体看代码：

public int reversePairs(int[] nums) {
        int n = nums.length;
        return merge(nums, new int[n], 0, n - 1);
    }

    /**
     * 归并排序，返回 [left, right] 区间内逆序对个数
     * @param nums
     * @param temp
     * @param left
     * @param right
     * @return
     */
    public int merge(int[] nums, int[] temp, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (left + right) >> 1;
        // 归并排序左半
        int leftCount = merge(nums, temp, left, mid);
        // 归并排序右半
        int rightCount = merge(nums, temp, mid + 1, right);
        // 左半最大元素不大于右半最小元素，证明两个区间合并后不会出现新的逆序对
        if (nums[mid] <= nums[mid + 1]) {
            return leftCount + rightCount;
        }
        // 合并左右区间并计算合并产生的逆序对
        int crossCOunt = mergeAndCount(nums, temp, left, right);
        return leftCount + rightCount + crossCOunt;
    }

    /**
     * 合并两个区间并计算合并产生的逆序对
     * 
     * @param nums
     * @param temp
     * @param left
     * @param right
     * @return
     */
    public int mergeAndCount(int[] nums, int[] temp, int left, int right) {
        // 先将合并区间元素拷贝到临时数组
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        // 左右区间边界
        int mid = (left + right) >> 1;
        // 做右指针
        int leftIdx = left;
        int rightIdx = mid + 1;
        // 逆序对个数
        int count = 0;
        // 合并区间
        for (int i = left; i <= right; i++) {
            if (leftIdx == mid + 1) {
                nums[i] = temp[rightIdx++];
            } else if (rightIdx == right + 1) {
                nums[i] = temp[leftIdx++];
            } else if (temp[leftIdx] <= temp[rightIdx]) {
                nums[i] = temp[leftIdx++];
            } else {    // 左指针当前元素大于右指针当前元素，统计逆序对个数
                count += mid - leftIdx + 1;
                nums[i] = temp[rightIdx++];
            }
        }
        return count;
    }
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67