1.题目链接
2.解题思路
- 这道题利用归并排序算法的性质，在排序过程中，来统计逆序对的个数，详见：解题思路。
3.出错代码
class Solution:
def __init__(self):
self.count = 0
def merge(self,nums,left,right,mid):
leftnums = nums[left:mid+1]
rightnums = nums[mid+1:right+1]
n1 = mid - left + 1
n2 = right - mid
i = 0
j = 0
k = left
while i < n1 and j < n2:
if leftnums[i] <= rightnums[j]:
nums[k] = leftnums[i]
i += 1
else:
nums[k] = rightnums[j]
j += 1
self.count += mid + 1 - i
k += 1
while i < n1:
nums[k] = leftnums[i]
k = k + 1
i = i + 1
while j < n2:
nums[k] = rightnums[j]
k += 1
j += 1
def mergesort(self,nums,left,right):
if right > left:
mid = left + (right - left)//2
self.mergesort(nums,left,mid)
self.mergesort(nums,mid+1,right)
self.merge(nums,left,right,mid)
def reversePairs(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
self.mergesort(nums,left,right)
return self.count
- 其中的reversePairs是题目的主接口，调用了mergesort函数，mergesort利用后续遍历的思想，先对前半部分排序，再对后半部分排序，之后再将前、后排序好的部分调用merge函数归并。其中merge函数首先对nums数字的前、后两半部分保存在leftnums和rightnums两个数组中，之后遍历两个数组归并。
4.出错部分分析
- 以上代码经过反复调试，始终不正确，无法找到出错的地方。后来第二天自己又默写了一遍代码，找到了逻辑不通的地方，出错的代码片段如下：
while i < n1 and j < n2:
if leftnums[i] <= rightnums[j]:
nums[k] = leftnums[i]
i += 1
else:
nums[k] = rightnums[j]
j += 1
self.count += mid + 1 - i
k += 1
- 在这个代码片段中 self.count += mid + 1 - i，总的逆序数对，要在leftnums[i] > rightnums[j]的时候进行更新，更新的值应该是mid+1-(left+i)，我错误的写成了mid + 1 - i（把i当成了"left"）。这种逻辑错误老实说还是比较难发现的。
