python merge sort solution


  • 0
    G
    # 1. merge sort from large number to small number
    # 2. save the original position of element of nums
    class Solution(object):
        def merge(self,nums,left,right,res):
            if left>=right:
                return
            mid=(left+right)>>1
            self.merge(nums,left,mid,res)
            self.merge(nums,mid+1,right,res)
            tmp,i,j=[],left,mid+1
            while i<=mid or j<=right:
                if i>mid:
                    tmp.append(nums[j])
                    j+=1
                elif j>right:
                    tmp.append(nums[i])
                    i+=1
                elif nums[i][0]>nums[j][0]:
                    res[nums[i][1]]+=right-j+1
                    tmp.append(nums[i])
                    i+=1
                else:
                    tmp.append(nums[j])
                    j+=1
            for i in range(left,right+1):
                nums[i]=tmp[i-left]
            
        def countSmaller(self,nums):
            n=len(nums)
            res=[0]*n
            data=[(nums[i],i) for i in range(n)]
            self.merge(data,0,n-1,res)
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.