题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
关键点在于利用归并排序统计逆序：
class Solution: count = 0 mod = 1000000007 def InversePairs(self , data: List[int]) -> int: # write code here def merge_sort(nums, left, right): if left >= right: return nums mid = left + ((right - left) >> 1) merge_sort(nums, left, mid) merge_sort(nums, mid + 1, right) i, j = left, mid + 1 sort_nums = [] while i <= mid and j <= right: if nums[i] < nums[j]: sort_nums.append(nums[i]) i += 1 else: sort_nums.append(nums[j]) self.count += (mid - i + 1) j += 1 sort_nums.extend(nums[i: mid + 1]) sort_nums.extend(nums[j: right + 1]) nums[left: right + 1] = sort_nums self.count %= self.mod return nums merge_sort(data, 0, len(data) - 1) return self.count去掉count的代码就是一个正常的归并排序，
要点在于当出现逆序时对第j个数字的逆序计数：
self.count += (mid - i + 1)返回时进行取模操作，其他不变。
