Python bisect solution, slow but AC


  • 3
    V
    import bisect
    class Solution(object):
        def countSmaller(self, nums):
            result = []
            sortedList = []
            for num in nums[::-1]:
                position=bisect.bisect_left(sortedList, num)
                result.insert(0,position)
                bisect.insort(sortedList,num)
            return result

  • 0
    S

    Actually, this logic is great and fast. result.insert takes a lot of time. you can try result.append(position) and then return res[::-1]. you will see your running time will around 170ms which is about half of your current running time.


  • 0
    S

    Tried, great idea


  • 0
    L

    Also, since you already get the position using bisect_left, you can just call bisect.insert(position, num), rather than bisect.insort(sortedList,num). That would save another log(n) binary search time.


  • 0
    A

    @leetcodedavy said in Python bisect solution, slow but AC:

    bisect.insert(position, num)

    Did you mean sortedList.insert(position, num)? Cause bisect module does not have an insert() method. Thanks.


Log in to reply
 

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