在合并的过程中统计逆序对的数量：
合并阶段 本质上是 合并两个排序数组 的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。
重点：如何在归并排序中记录逆序对的数量的，沿用归并排序的模板
方法一：采用暴力解法
采用两层循环来写
class Solution:
def reversePairs(self, nums: List[int]) -> int:
res = 0
for i in range(len(nums)-1):
for j in range(i +1,len(nums)):
if nums[i] >nums[j]:
res +=1
运行结果：超时
方法二：采用归并排序的思路来解题
复杂度分析：
时间复杂度 O(NlogN)： 其中 N为数组长度；归并排序使用 O(NlogN) 时间；
空间复杂度 O(N)： 辅助数组 tmptmptmp 占用 O(N)大小的额外空间
class Solution:
def reversePairs(self, nums: List[int]) -> int:
def merge_sort(nums, left, right):
#子数组长度为1，终止划分，需要开始解决
if left >= right:
return 0
#计算数组的中间位置
mid = left + (right - left) // 2
#调用merge_sort函数，递归划分左子数组
cnt_l = merge_sort(nums, left, mid)
#调用merge_sort函数，递归划分右子数组
cnt_r = merge_sort(nums, mid + 1, right)
#调用merge函数，将nums数组中三块区域合并
cnt_c = merge(nums, left, mid, right)
return cnt_l + cnt_r + cnt_c
def merge(nums, left, mid, right):
#初始化变量以及数组，用于合并阶段暂存元素以及统计逆序对
tmp, cnt = [], 0
#定义双指针，分别指向左右子数组的首元素
l1, l2 = left, mid + 1
#循环合并
#循环条件：左区间的首元素<=中间元素，并且右区间的首元素<=末尾元素
while l1 <= mid and l2 <= right:
#左区间的首元素<右区间的首元素，不需要动逆序对的数量
if nums[l1] <= nums[l2]:
tmp.append(nums[l1])
l1 += 1
#左边的数和右边的数共同组成了逆序对
else:
tmp.append(nums[l2])
l2 += 1
cnt += (mid - l1 + 1) #统计逆序对数
# 如果左区间中还有元素，那么把它都添加到 result 中
if l1 <= mid:
tmp.extend(nums[l1 : mid + 1])
# 如果右区间中还有元素，那么把它都添加到 result 中
else:
tmp.extend(nums[l2 : right + 1])
#把新数组中的数覆盖nums数组
nums[left : right + 1] = tmp[:]
return cnt
return merge_sort(nums, 0, len(nums) - 1)
class Solution:
def reversePairs(self, nums: List[int]) -> int:
def merge_sort(l, r):
# 终止条件
if l >= r: return 0
# 递归划分
m = (l + r) // 2
res = merge_sort(l, m) + merge_sort(m + 1, r)
# 合并阶段
i, j = l, m + 1
#做一个拷贝操作
tmp[l:r + 1] = nums[l:r + 1]
for k in range(l, r + 1):
#左子数组已经合并完成，添加右子数组当前元素
#逆序对数不变
if i == m + 1:
nums[k] = tmp[j]
j += 1
#右子数组已合并完成以及左区间的首元素<右区间的首元素，添加左子数组当前元素
#逆序对数不变
elif j == r + 1 or tmp[i] <= tmp[j]:
nums[k] = tmp[i]
i += 1
#左边的和右边的共同组成逆序对数，添加右子数组当前元素
else:
nums[k] = tmp[j]
j += 1
res += m - i + 1 # 统计逆序对
return res
#初始化：辅助数组，用于合并阶段暂存元素
tmp = [0] * len(nums)
#返回值：执行归并排序merge_sort，并返回逆序对总数
return merge_sort(0, len(nums) - 1)