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

题目描述

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

输入输出

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

基本思路

可以从归并排序中获得思路。

求逆序对和归并排序又有什么关系呢？关键就在于「归并」当中「并」的过程。我们通过一个实例来看看。假设我们有两个已排序的序列等待合并，分别是 L = {8, 12, 16, 22, 100 } 和 R = {9, 26, 55, 64, 91}。一开始我们用指针 lPtr = 0 指向 L 的首部，rPtr = 0 指向 R 的头部。记已经合并好的部分为 M。

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

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

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

这个时候我们把左边的 8 加入了答案，我们发现右边没有数比 8 小，所以 88 对逆序对总数的「贡献」为 0。

接着我们继续合并，把 9 加入了答案，此时 lPtr 指向 12，rPtr 指向 26。

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

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

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

java实现

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
class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        this.count = 0;
        sort(nums, 0, nums.length-1, new int[nums.length]);
        return count;
    }

    public void sort(int[] nums, int left, int right, int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            sort(nums, left, mid, temp);
            sort(nums, mid+1, right, temp);
            merge(nums, left, mid, right, temp);
        }
    }

    public void merge(int[] nums, int left, int mid, int right, int[] temp){
        int i = left;//左部分首元素
        int j = mid + 1;//右部分首元素
        int t = 0;

        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                temp[t++] = nums[i++];
            }else{
                count += mid + 1 - i;//关键代码
                temp[t++] = nums[j++];
            }
        }
        while(i <= mid){//左表还有剩余
            temp[t++] = nums[i++];
        }
        while(j <= right){//右表还有剩余
            temp[t++] = nums[j++];
        }

        t = 0;
        while(left <= right){//将temp数组中的元素全部copy回nums中
            nums[left++] = temp[t++];
        }
    }
}