在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
参考题解：
https://www.bilibili.com/video/BV1Qk4y1r7u5?zw
思路及算法
什么是逆序对？
「如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对」
在 [3,1,2] 中
(3,1) 就是一个逆序对
解法1：暴力法
用两个 for 循环逐个进行比较
class Solution:
def reversePairs(self, nums) -> int:
size = len(nums)
if size < 2:
return 0
res = 0
for i in range(0, size - 1):
for j in range(i + 1, size):
if nums[i] > nums[j]:
res += 1
return res
解法2：归并排序
为什么用「归并排序」？
在高级排序算法（归并排序、快速排序）中，能够看到非常明显的阶段性排序结果的算法就是归并排序
执行步骤
- （分）将数组“分割”成不可再分
- （并）将两个有序数组合并，在合并过程中，判断是否有满足「逆序对」的情况
什么情况下会出现逆序对，举例：
计算 符合j 位置元素的「逆序对」个数，我们一眼可以看出， 2 3 5 7 都可以与 索引为j的元素组成「逆序对」。实际上，我们并不需要具体知道是哪些元素构成逆序对。
arr[i] > arr[j]依靠两个有序数组分别有序， 所以 [i ... mid+1] 内的元素都是符合「逆序对」
所以，计算 j位置符合逆序对的元素个数的公式为： mid - i + 1
动态演示
https://www.bilibili.com/video/BV1Qk4y1r7u5?t=5m30s
边想边写
- 顶层函数
class Solution:
def reversePairs(self, nums: List[int]) -> int:
size = len(nums)
if size < 2:
return 0
# 创建等同长度的空数组
self.nums_copy = [0 for _ in range(size)]
# 逆序对个数
self.count = 0
self.helper(nums, 0, size-1)
return self.count
def helper(nums, left, right):
pass
def merge_two_sorted_array(arr, left, mid, right):
pass
- “分割”数组
def helper(self, nums, left, right):
if left == right:
return
mid = (left + right) >> 1
# 左 nums[left .. mid]
# 右 nums[mid+1 .. right]
self.helper(nums, left, mid) # 左边有序
self.helper(nums, mid + 1, right) # 右边有序
self.merge_two_sored_arr(nums, left, mid, right)
优化：
如果 右边的起始元素（排序后的第一个元素） 大于 左边的尾部元素（排序后的最后一个元素） 说明，右边部分整体大于左边，即不用进行合并操作
def helper(self, nums, left, right):
if left == right:
return
mid = (left + right) >> 1
# 左 nums[left .. mid]
# 右 nums[mid+1 .. right]
self.helper(nums, left, mid) # 左边有序
self.helper(nums, mid + 1, right) # 右边有序
# 优化
if nums[mid] <= nums[mid+1]:
return
self.merge_two_sored_arr(nums, left, mid, right)
- 合并两个有序数组
「归并排序」 中的合并两个有序数组
def merge_two_sorted_array(arr, left, mid, right):
# 因为nums_for_compare 默认是空的，所以我们需要在对应索引位置赋值
for i in range(left, right + 1):
nums_for_compare[i] = arr[i]
p1 = left # 左边数组起始位置索引
p2 = mid + 1 # 右边数组起始位置索引
for k in range(left, right + 1):
if p1 >= mid + 1:
# 左边走完了
arr[k] = nums_for_compare[p2]
p2 += 1
elif p2 > right:
# 右边走完了
arr[k] = nums_for_compare[p1]
p1 += 1
elif nums_for_compare[p1] < nums_for_compare[p2]:
arr[k] = nums_for_compare[p1]
p1 += 1
else:
arr[k] = nums_for_compare[p2]
p2 += 1
我们需要在 归并 的过程中，计算出「逆序对」的个数，再对合并函数进行修改
def merge_two_sorted_array(arr, left, mid, right):
# 因为nums_for_compare 默认是空的，所以我们需要在对应索引位置赋值
for i in range(left, right + 1):
nums_for_compare[i] = arr[i]
p1 = left # 左边数组起始位置索引
p2 = mid + 1 # 右边数组起始位置索引
for k in range(left, right + 1):
if p1 >= mid + 1:
# 左边走完了
arr[k] = nums_for_compare[p2]
p2 += 1
elif p2 > right:
# 右边走完了
arr[k] = nums_for_compare[p1]
p1 += 1
elif nums_for_compare[p1] < nums_for_compare[p2]:
arr[k] = nums_for_compare[p1]
p1 += 1
else:
# 满足，则出现逆序对
arr[k] = nums_for_compare[p2]
p2 += 1
# 逆序对个数
self.count += mid - p1 + 1
再次解释，mid - p1 + 1是如何计算逆序对个数的
两个小数组，都是单调递增。nums_for_compare[p1] > nums_for_compare[p2] 就意味着，[p1 ... mid + 1] 内的元素都是大于 p2所指的元素。
完整代码
class Solution:
def reversePairs(self, nums: List[int]) -> int:
size = len(nums)
if size < 2:
return 0
self.nums_copy = [0 for _ in range(size)]
self.count = 0
self.helper(nums, 0, size-1)
return self.count
def helper(self, nums, left, right):
if left == right:
return
mid = (left + right) >> 1
# 左 nums[left .. mid]
# 右 nums[mid+1 .. right]
self.helper(nums, left, mid)
self.helper(nums, mid + 1, right)
if nums[mid] <= nums[mid + 1]:
return
self.merge_two_sored_arr(nums, left, mid, right)
def merge_two_sored_arr(self, nums, left, mid, right):
for x in range(left, right + 1):
self.nums_copy[x] = nums[x]
i = left
j = mid + 1
for k in range(left, right+1):
if i == mid + 1:
nums[k] = self.nums_copy[j]
j += 1
elif j == right + 1:
nums[k] = self.nums_copy[i]
i += 1
elif self.nums_copy[i] <= self.nums_copy[j]:
nums[k] = self.nums_copy[i]
i += 1
else:
nums[k] = self.nums_copy[j]
j += 1
self.count += mid - i + 1