4、剑指 Offer 51. 数组中的逆序对
一、题目
剑指 Offer 51. 数组中的逆序对 难度困难
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
二、解法
2.1、归并排序统计法
核心思路：
求逆序对和归并排序有什么关系呢？关键就在于「归并」当中「并」的过程。
归并排序体现了 “分而治之” 的算法思想，具体为：
- 分： 不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题；
- 治： 划分到子数组长度为 1 时，开始向上合并，不断将 较短排序数组 合并为 较长排序数组，直至合并至原数组时完成排序；
合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。
举个例子来说明：假设我们有两个已排序的序列等待合并，分别是 L = { 8, 12, 16, 22, 100 } 和 R = { 9, 26, 55, 64, 91 } 。一开始我们用指针 i = 0 指向 L 的首部，j = 0 指向 R 的头部。记已经合并好的部分为 M 。
L = [8, 12, 16, 22, 100] R = [9, 26, 55, 64, 91] M = []
| |
i j
我们发现 i 指向的元素小于 j 指向的元素，于是把 i 指向的元素放入答案，并把 i 后移一位。这个时候我们把左边的 8 加入了答案，此时右边没有数比 8 小。
L = [8, 12, 16, 22, 100] R = [9, 26, 55, 64, 91] M = [8]
| |
i j
接着我们继续合并，此时i指向的元素（12）大于j指向的元素（9），那么我们可知i后面的元素也大于 9 ，也就是 12/16/22/100 都大于 9 ，由此我们就得到了 4 对逆序对。
然后把 9 加入答案，此时 i 指向 12，j 指向 26 。
L = [8, 12, 16, 22, 100] R = [9, 26, 55, 64, 91] M = [8, 9]
| |
i j
以此类推，等合并完这两个已排序的序列后，我们就算出了本轮的逆序对数量。
因此，本题的关键是使用归并排序中的合并阶段来统计逆序对数量的。
复杂度分析：
- 时间复杂度 O(N * log N)： 其中 N 为数组长度；归并排序使用 O(N * log N) 时间；
- 空间复杂度 O(N)*O*(*N*) ： 辅助数组 tmp 占用 O(N) 大小的额外空间；
代码：
为简化代码，「 当 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 left, int right) {
// 终止条件
if (left >= right) return 0;
// 递归划分
int mid = (left + right) / 2;
int result = mergeSort(left, mid) + mergeSort(mid + 1, right);
// 合并阶段
int i = left, j = mid + 1;
// 将 left~right 区间的值拷贝到 tmp 数组的对应区间中
for (int k = left; k <= right; k++)
tmp[k] = nums[k];
// 根据 tmp 中对应区间的值操作 nums 数组
for (int k = left; k <= right; k++) {
if (i == mid + 1)
// i 已经走到尽头
nums[k] = tmp[j++];
else if (j == right + 1 || tmp[i] <= tmp[j])
// j 已经走到尽头 || j 位置的值比 i 位置的值大
nums[k] = tmp[i++];
else {
// i 位置的值比 j 位置的值大
nums[k] = tmp[j++];
// 统计逆序对（ 推论：i~mid 位置的数都比 j 位置的数大，因此此次统计到的逆序对数量为 mid-i+1 ）
result += mid - i + 1;
}
}
return result;
}
}
REF
官方题解：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/
评论区题解：