剑指 Offer 51题：数组中的逆序对

1.题目描述

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

示例1：

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

2.思路分析

「归并排序」与「逆序对」是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：

分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题； 治： 划分到子数组长度为 1 时，开始向上合并，不断将 较短排序数组 合并为 较长排序数组，直至合并至原数组时完成排序；

如下图所示，为数组 [7, 3, 2, 6, 0, 1, 5, 4] 的归并排序过程。

合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。

因此，考虑在归并排序的合并阶段统计「逆序对」数量，完成归并排序时，也随之完成所有逆序对的统计。

实际上，只需要在归并排序的代码中加一行程序即可解决本题

如下图所示，为左子数组 [2, 3, 6, 7] 与 右子数组 [0, 1, 4, 5] 的合并与逆序对统计过程。（部分）

2.1 初始化

2.2 依次比较并进行归并排序和逆序对的统计

后面的步骤同理，此处省略......

3.解答

class Solution {
    //归并排序，求逆序对
    
    //统计逆序对的数量
    int count = 0;

    public int reversePairs(int[] nums) {
        //归并排序的同时统计逆序对的数量
        mergeSoer(nums, 0, nums.length - 1);

        return count;
    }

    //辅助方法：归并排序
    public void mergeSoer(int[] arr, int low, int high) {
        int middle = (high+low)/2;
        if(low < high) {
            // 处理左边
            mergeSoer(arr, low, middle);
            // 处理右边
            mergeSoer(arr, middle+1, high);
            // 归并
            merge(arr, low, middle, high);
        }
    }

    //辅助方法：合并区间
    public void merge(int[] arr, int low, int middle, int high) {
        // 用于存储归并后的临时数组
        int[] temp = new int[high-low+1];
        // 记录第一个数组中需要遍历的下标
        int i = low;
        // 记录第二个数组中需要遍历的下标
        int j = middle + 1;
        // 记录临时数组中的下标
        int index = 0;

        while(i <= middle && j <= high) {
            if(arr[i] <= arr[j]) {
                temp[index] = arr[i];
                i++;
            }else {
                //统计逆序对的数量
                count = count + (middle - i + 1);
                temp[index] = arr[j];
                j++;
            }
            index++;
        }

        // 处理剩下的数据
        while(i <= middle) {
            temp[index] = arr[i];
            i++;
            index++;
        }
        while(j <= high) {
            temp[index] = arr[j];
            j++;
            index++;
        }

        // 把临时数组temp中的元素返回arr中
        for(int k = 0; k < temp.length; k++) {
            arr[k+low] = temp[k];
        }
    }
}

时间复杂度 O(N log N) ： 其中 N 为数组长度；归并排序使用 O(N log N) 时间； 空间复杂度 O(N) ： 辅助数组 tmp 占用 O(N)大小的额外空间；