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]
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."
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.