LeetCode 剑指 Offer 51. 数组中的逆序对 归并题解，理解归并排序，学习新的解题思路。

题目

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

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 限制：

0 <= 数组长度 <= 50000

暴力解

暴力的思路最容易想到，但是题干中限制了数组长度可以为 50000，暴力解50000^2的复杂度下运行会超时。

复杂度分析

循环套循环，O(n^2)时间复杂度。使用了一个cnt变量存储结果，空间复杂度O(1)。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int reversePairsBruteForce(int[] nums) {
    int cnt = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] > nums[j]) {
                ++cnt;
            }
        }
    }
    return cnt;
}

归并排序解

归并排序是本题正解，回顾下归并排序：

https://github.com/redolog/algorithm-java/blob/main/src/main/java/com/algorithm/sort/MergeSort.java

思路

解题关键：

  1. 首先是熟悉归并排序（不太可能你在解这道题的时候发明归并排序）；
  2. 其次，理解分治合并数组时的操作，合并左右两个数组时：
    1. 递归执行序可以保证我们每次进入merge()时，左右两个数组分别已经有序；
    2. 左右两个数组进行比较，临时数组插入当前左右数据中较小的那个。既然有较小，对应就有较大，如果较大元素此时在在左数组，那么此元素+此元素在左数组中的后续元素，均大于右数组当前元素；
    3. 综上，可以计数；

对于没有刷题经验的我来说，首先是通过这个例子看别人的题解，能经过提示或者看懂归并题解的情况下落地自己的代码。

后续，此思路经过练习即可内化。

代码

 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

public class ReversePairs {

    int cnt;

    /**
     * 执行用时：
     * 31 ms
     * , 在所有 Java 提交中击败了
     * 69.49%
     * 的用户
     * 内存消耗：
     * 49 MB
     * , 在所有 Java 提交中击败了
     * 55.76%
     * 的用户
     * 通过测试用例：
     * 139 / 139
     */
    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return cnt;
    }

    private void mergeSort(int[] nums, int leftIdx, int rightIdx) {
        if (leftIdx >= rightIdx) {
            return;
        }
        int midIdx = leftIdx + ((rightIdx - leftIdx) >> 1);
        mergeSort(nums, leftIdx, midIdx);
        mergeSort(nums, midIdx + 1, rightIdx);
        merge(nums, leftIdx, midIdx, rightIdx);
    }

    private void merge(int[] nums, int leftIdx, int midIdx, int rightIdx) {
        int[] tmpArr = new int[rightIdx - leftIdx + 1];

        int i = leftIdx;
        int j = midIdx + 1;
        // tmpArr 存储指针
        int t = 0;

        while (i <= midIdx && j <= rightIdx) {
            if (nums[i] <= nums[j]) {
                tmpArr[t++] = nums[i++];
            } else {
                cnt += midIdx - i + 1;
                tmpArr[t++] = nums[j++];
            }
        }

        while (i <= midIdx) {
            tmpArr[t++] = nums[i++];
        }
        while (j <= rightIdx) {
            tmpArr[t++] = nums[j++];
        }

        for (t = 0; t < tmpArr.length; t++) {
            nums[leftIdx + t] = tmpArr[t];
        }
    }
}