class Solution:
def reversePairs(self, nums: List[int]) -> int:
n = len(nums)
t = [0]*n
return self.fenZhiSort(nums,0,n-1,t)
def fenZhiSort(self,nums,l,r,t):
if l >= r:
return 0
mid = (l + r) // 2
pairs = self.fenZhiSort(nums,l,mid,t) +self.fenZhiSort(nums,mid + 1,r,t)
i,j,pos = l,mid+1,l
while i <= mid and j<= r:
if nums[i] > nums[j]:
t[pos] = nums[j]
j += 1
else:
t[pos] = nums[i]
i += 1
pairs += j - mid - 1
pos += 1
t[pos:mid+1-i] = nums [i:mid+1]
pairs += (j - mid - 1)*(mid+1-i)
pos = mid + 1
t[pos:r+1-j] = nums [j:r+1]
pairs += (i - r - 1)*(r+1-j)
nums[l:r+1] = t[l:r+1]
return pairs
网友评论