题解 |【清晰图解】 #数组中的逆序对#"分而治之"妙啊

已默认你已读懂题意了哈

我的解题思路如下

其实我觉得归并排序是跟逆序对是息息相关的，因为归并本质体现的是一种 “分而治之” 的思想

那问题来了？

• 怎么分： 不断从数组的中点位置划开（即二分法），然后把整个数组的排序问题转化成一个子数组的排序问题；

• 怎么治： 划分到子数组它的长度为 1 时，开始向上合并，不断把 较短排序数组 合并成 较长排序数组，这样直到合并成原数组就完成排序了啊；

举个例

下面是数组 [7,3,2,6,0,1,5,4] 的归并排序

看上面的图是合并阶段

本质上是合并两个已经排好序的数组的过程，而每当遇到 左子数组的当前元素 > 右子数组的当前元素 的时候，意味着左边子数组的当前元素 到 末尾元素 和 右边子数组的当前元素构成了若干的逆序对；

我们把左边子数组 [2, 3, 6, 7]和右边子数组 [0, 1, 4, 5] 的合并与逆序来演示下

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

算法描述

• 终止条件是啥： 当 l≥r 时，代表着子数组长度是 1 ，此时必须终止划分；
• 递归划分： 先算数组中点m在哪里， 然后递归划分左边子数组 merge_sort(l, m) 以及右边子数组 merge_sort(m + 1, r)；

合并与逆序思路如下

先把数组nums的闭区间[i,r]内的元素至移动到辅助数组tmp里面； 然后设置双指针 i, j分别指向左/右子数组的第一个元素；

• 当i=m+1时：代表的是左边子数组已合并完了，所以添加右边子数组当前元素tmp[j]，并执行 j=j+1；
• 否则，当j=r+1时：代表的是右子数组已经合并完了，所以添加左子数组当前元素tmp[i]，并执行i=i+1；
• 否则，当tmp[i]≤tmp[j]时：添加左边子数组的当前元素即tmp[i] ，并执行i=i+1；
• 否则（即tmp[i]>tmp[j]）时： 添加右子数组当前元素即tmp[j] ，并执行j=j+1；此时构成m−i+1个「逆序对」，统计添加至resres 也就是返回值，代表的是目前返回的逆序对总数 resres；

为了简化代码，j=r+1 时 和 当 tmp[i]≤tmp[j] 的时侯，两判断表达式可以合并。

class Solution {
    int[] nums, tmp;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }
    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                nums[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
}

主方法完成两件事

• 对辅助数组 tmp 进行初始化，用于合并阶段暂存元素；
• 然后执行归并排序方法 merge_sort()，并返回逆序对总数即可；

举个例子

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

复杂度分析下

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