O(nlog(n)) Python solution, easy understanding


  • 0
    K
    class Solution(object):
        def countSmaller(self, nums):
            """
            :type nums: List[int]
            :rtype: List[int]
            """
            def insert(num):
                if not snums:
                    snums.append(num)
                    return 0
                else:
                    p0,p1 = 0,len(snums)
                    while p0 < p1:
                        mid = (p0+p1)/2
                        if snums[mid] < num:
                            p0 = mid + 1
                        else:
                            p1 = mid
                    snums.insert(p0,num)
                    return p0
            snums = []
            ans = []
            for i in xrange (len(nums)-1,-1,-1):
                tmp = nums[i]
                ans.append(insert(tmp))
            return ans[::-1]
    

    The basic idea is read the number from the left of the nums, than put it in a sorted array and return its index(imply how many numbers are smaller than it.

    If you have any better idea, pls tell me , thank you!


Log in to reply
 

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