【归并排序, 暴力, 遍历】数组中的逆序对

题目

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

---

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

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

解题

方法一：暴力遍历

思路

暴力遍历每一个元素，再遍历该元素后面的所有元素，如果该元素比后面的大则逆序对增加。
(超时)

代码

class Solution {
    public int reversePairs(int[] nums) {
        int len = nums.length;
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[i] > nums[j]) {
                    ans++;
                }
            }
        }

        return ans;
    }
}

方法二：归并排序

思路

在归并排序的合并过程中。
假设我们有两个已排序的序列等待合并，分别是 $L={8,12,16,22,100}$ 和 $R = \{ 9, 26, 55, 64, 91 \}$。一开始我们用指针 lPtr = 0 指向 $L$ 的首部，rPtr = 0 指向 $R$ 的头部。记已经合并好的部分为 $M$。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = []
     |                          |
   lPtr                       rPtr

我们发现 lPtr 指向的元素小于 rPtr 指向的元素，于是把 lPtr 指向的元素放入答案，并把 lPtr 后移一位。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8]
        |                       |
      lPtr                     rPtr

这个时候我们把左边的 $8$ 加入了答案，我们发现右边没有数比 $8$ 小，所以 $8$ 对逆序对总数的「贡献」为 $0$。
接着我们继续合并，把 $9$ 加入了答案，此时 lPtr 指向 $12$，rPtr 指向 $26$。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8, 9]
        |                          |
       lPtr                       rPtr

此时 lPtr 比 rPtr 小，把 lPtr 对应的数加入答案，并考虑它对逆序对总数的贡献为 rPtr 相对 $R$ 首位置的偏移 $1$（即右边只有一个数比 $12$ 小，所以只有它和 $12$ 构成逆序对），以此类推。

我们发现用这种「算贡献」的思想在合并的过程中计算逆序对的数量的时候，只在 lPtr 右移的时候计算，是基于这样的事实：当前 lPtr 指向的数字比 rPtr 小，但是比 RR 中 [0 ... rPtr - 1] 的其他数字大，[0 ... rPtr - 1] 的其他数字本应当排在 lPtr 对应数字的左边，但是它排在了右边，所以这里就贡献了 rPtr 个逆序对。

代码

class Solution {
    public int[] helper;
    public int ans;
    
    public int reversePairs(int[] nums) {
        helper = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return ans;
    }

    public void mergeSort(int[] nums, int start, int end) {
        if (start < end) {
            int mid = start + ((end - start) >> 1);
            mergeSort(nums, start, mid);
            mergeSort(nums, mid + 1, end);
            merge(nums, start, end, mid);
        }
    }

    public void merge(int[] nums, int start, int end, int split) {
        System.arraycopy(nums, start, helper, start, end - start + 1);
        int fstHalfIdx = start, secHalfIdx = split + 1, numsIdx = start;
        while (fstHalfIdx <= split && secHalfIdx <= end) {
            if (helper[fstHalfIdx] <= helper[secHalfIdx]) {
                nums[numsIdx++] = helper[fstHalfIdx++];
            } else {
                nums[numsIdx++] = helper[secHalfIdx++];
                ans += split - fstHalfIdx + 1;
            }
        }

        while(fstHalfIdx <= split) {
            nums[numsIdx++] = helper[fstHalfIdx++];
        }
    }
}