剑指Offer51-数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
- 0 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：力扣
一解
使用归并排序算法，不熟悉该算法的建议查看官方题解：
class Solution:
def merge_sort(self, nums, tmp, l, r):
if l >= r: return 0
mid = l + (r - l) // 2
res = self.merge_sort(nums, tmp, l, mid) + self.merge_sort(nums, tmp, mid + 1, r)
i, j, pos = l, mid + 1, l
while i <= mid and j <= r:
if nums[i] > nums[j]:
tmp[pos] = nums[j]
res += mid + 1 - i
j += 1
else:
tmp[pos] = nums[i]
i += 1
pos += 1
for k in range(i, mid + 1):
tmp[pos] = nums[k]
pos += 1
for k in range(j, r+1):
tmp[pos] = nums[k]
pos += 1
nums[l:r + 1] = tmp[l: r + 1]
return res
def reversePairs(self, nums: List[int]) -> int:
tmp = [0]*len(nums)
return self.merge_sort(nums, tmp, 0, len(nums) - 1)