Use Python insert sort algorithms from end, O(n*log(n))


  • -1
    W
    class Solution(object):
        def countSmaller(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            n=len(nums)
            if n==0:
                return []
            p=[0]
            for i in range(n-2,-1,-1):
                low,high=i+1,n-1
                a=nums[i]
                mid=(high+low)/2
                while high>low+1:
                    mid=(high+low)/2
                    if a>nums[mid]:
                        high=mid
                    else:
                        low=mid
                if a>nums[low]:
                        mid=low
                else:
                    for j in range(low,high+1):
                        if a<=nums[j]:
                            mid=j+1
                p.append(n-mid)
                nums.insert(mid,a)
                nums.pop(i)
            return p[::-1]

Log in to reply
 

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