美文网首页
啊来不及写了

啊来不及写了

作者: Never肥宅 | 来源:发表于2020-04-24 01:23 被阅读0次

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

相关文章

网友评论

      本文标题:啊来不及写了

      本文链接:https://www.haomeiwen.com/subject/bgvtwhtx.html