Python's bisect module, O(n) add and O(1) return median


  • 2
    O

    For people that could accept the build-in module solutions, there is also a module called bisect that could do the jobs~, the complexity should be O(n) adding (*thanks @StefanPochmann's reminding) and O(1) finding the median

    import bisect
    class MedianFinder:
        def __init__(self):
            self.nums = []
    
        def addNum(self, num):
            bisect.insort(self.nums, num)
    
        def findMedian(self):
            nums = self.nums
            if len(nums) % 2 == 0:
                return (nums[len(nums)/2] + nums[len(nums)/2-1]) / 2.0
            else:
                return nums[len(nums)/2]

  • 1

    No, bisect.insort isn't O(log n) but only O(n). The documentation even reminds you of it:

    "Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step."


  • 0
    O

    ha, so embarrassed XD Thanks for reminding!


  • 0

    Well, you're probably by far not the first who made that mistake :-P

    Btw, an alternative way to compute the median:

    def findMedian(self):
        nums = self.nums
        n = len(nums) / 2
        return (nums[n] + nums[~n]) / 2.
    

  • 0
    O

    oh damnnn, I forget the beautiful ~n trick!! nice!


  • 0

    Hahahaha, guess what... for the OJ test suite, your solution is, despite the bad complexity class, the fastest Python solution posted so far :-). Even though the OJ test suite does have a case with n > 20000.


  • 0
    O

    haha cool, totally unexpectedlyXD


Log in to reply
 

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