Count Inversions
给定一个整数列表 nums，返回逆序对的数量：满足 i < j 且 nums[i] > nums[j] 的索引对，也就是较大的值出现在较小的值之前。相等的值不会构成逆序对，排序后的列表中没有逆序对。
函数
- numsinteger-array
- 整数列表
- 返回值integer
- 满足 i < j 且 nums[i] > nums[j] 的数对数量
约束条件
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- 答案至多为
n(n-1)/2 < 2 × 108，因此可以用有符号 32 位整数表示。
示例
- 输入
- nums = [5, 3, 8, 1, 4]
- 输出
- 6
- 解释
- 5 排在 3、1 和 4 前面：有 3 对。3 排在 1 前面，8 排在 1 和 4 前面：又有 3 对。1 和 4 的顺序正确，所以总数是 6。
- 输入
- nums = [2, 2, 2, 1]
- 输出
- 3
- 解释
- 这 3 个 2 都在 1 前面，所以有 3 个逆序对。两个相等的 2 不计入，因为逆序对要求前面的值严格大于后面的值。
- 输入
- nums = [-1, 0, 7, 7]
- 输出
- 0
- 解释
- 列表已排序，两个相等的 7 不计入，因此答案是 0。
进阶
如果只有当 nums[i] > 2 × nums[j] 时，一对数才计数，会有什么变化？归并排序还能在 O(n log n) 时间内统计这些数对吗？
提示
逐个打开提示，每个都会多透露一点。
将列表分成左半部分和右半部分。每个逆序对要么在左半部分内，要么在右半部分内，要么由两侧各一个值组成。你能分别统计这三类吗？
对每一半进行排序，不会改变跨越中间位置的数对数量，因为每个左半部分的值仍然位于每个右半部分的值左侧。两半都排好序后，你就可以批量统计跨越中间位置的数对，而不必逐个统计。
使用归并排序。合并两个已排序的部分时，每次从右半部分取一个值，它都小于左半部分中所有尚未取出的值，因此要加上左半部分剩余的值的数量。遇到相等的值时，从左半部分取，这样相等的值就不会被计入。
题解
检查每一对大约需要进行 n² / 2 次比较。归并排序会批量统计数对：合并时，如果右半部分的一个值被放入结果，那么左半部分中所有仍在等待的值都比它大，而且原本排在它前面。一次减法就能统计整个批次，因此计数不会增加 O(n log n) 排序之外的开销。
检查每一对
结果正确，但无法在最大的测试中运行完毕
思路
对于每个索引 i，检查它后面的每个索引 j，当 nums[i] > nums[j] 时加 1。这就是定义，严格比较会排除相等的值。
需要进行 n(n-1)/2 次比较：对于 2 × 10^4 个值，几乎要比较 2 × 10^8 次；而 n 加倍时，比较次数会变为四倍。
算法
- 将
count = 0。 - 对于从 0 到
n-1的每个i，以及从i + 1到n-1的每个j，当nums[i] > nums[j]时，将count加 1。 - 返回
count。
def countInversions(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] > nums[j]:
count += 1
return count在合并时计数的归并排序
思路
将列表从中间拆分。一个逆序对中的两个值都在左半部分、都在右半部分，或者分别位于两边。对每一半递归处理，可以统计前两种逆序对，并对该半部分排序。排序只会移动同一半中的值，所以每个左侧值仍然排在每个右侧值之前，跨越两边的数对也不会改变。
合并时，如果 left[i] ≤ right[j]，就放入 left[i]：仍在等待处理的每个右侧值都不小于 right[j]，所以它们不会构成逆序对。否则，right[j] 小于 left[i]，而且由于左半部分已排序，它也小于所有仍在等待处理的左侧值。将这些左侧值的数量加上。值相等时先放入左侧值，这样相等的值就不会构成逆序对。
对于 [5, 3, 8, 1, 4]，两半分别包含 1 个和 2 个逆序对。合并 [3, 5] 和 [1, 4, 8] 时，1 越过 3 和 5，4 越过 5：1 + 2 + 3 = 6。
算法
- 复制
nums，并创建一个长度相同的缓冲区。 - 如果范围内的值少于 2 个，则排序并计数后返回 0。
- 否则，在
mid处分开，并分别对两半进行排序和计数。 - 通过缓冲区合并两半：当
left[i] ≤ right[j]时，取左侧的值；否则取右侧的值，并加上尚未放置的左侧值的数量。 - 将合并后的范围复制回去，并返回三个计数的总和。
def sortAndCount(a, buf, lo, hi):
# Sorts a[lo:hi] and returns the number of inversions inside it.
if hi - lo < 2:
return 0
mid = (lo + hi) // 2
count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
# Merge the two sorted halves, counting the pairs that cross the middle.
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
buf[k] = a[i]
i += 1
else:
# a[j] is smaller than every left value not placed yet: a[i..mid-1].
buf[k] = a[j]
j += 1
count += mid - i
k += 1
while i < mid:
buf[k] = a[i]
i += 1
k += 1
while j < hi:
buf[k] = a[j]
j += 1
k += 1
a[lo:hi] = buf[lo:hi]
return count
def countInversions(nums):
a = list(nums) # sort a copy, not the caller's list
return sortAndCount(a, [0] * len(a), 0, len(a))
易错点和边界情况
- 放入一个右侧的值时加 1。它会通过所有仍在等待的左侧值，因此要加上它们的数量，即
mid - i。 - 值相等时取右侧的值，并用
left[i] < right[j]作为左侧的判断条件。这样一来，[2, 2, 2, 1]会把相等的 2 两两计数，结果会大于 3。请使用≤。 - 其中一半用完后，复制剩余值时仍然计数。左侧剩余的值后面没有右侧的值，而右侧剩余的值已经与每个左侧的值比较过了。
常见问题3
数组中的逆序对是什么？
逆序对是一对满足 i < j 的位置，其中 nums[i] > nums[j]，也就是说，较大的值排在较小的值前面。已排序的列表有 0 个逆序对，而由不同值组成的逆序列表有最多的逆序对，即 n(n-1)/2 个。逆序对的数量等于冒泡排序执行的相邻交换次数。
使用归并排序统计逆序对的时间复杂度是多少？
时间复杂度为 O(n log n)，合并缓冲区需要 O(n) 的额外空间。每一层合并都会访问每个值一次，log n 层大约需要 3 × 10^5 步，处理 2 × 10^4 个值。逐对处理的循环是 O(n²)。
不使用归并排序也能统计逆序对吗？
是的。对这些值的排名建立 Fenwick 树（二进制索引树），遍历列表一次，并对每个值查询有多少个更早出现的值比它大，每个值需要 O(log n)。总时间复杂度也是 O(n log n)。跟踪子树大小的平衡搜索树也能以同样的方式工作。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def countInversions(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [5, 3, 8, 1, 4]
预期输出
6