Skip to content

Instantly share code, notes, and snippets.

@onemouth
Created August 4, 2019 12:25
Show Gist options
  • Save onemouth/4bc2fa52650ee8be4c6f4555d55e7bee to your computer and use it in GitHub Desktop.
Save onemouth/4bc2fa52650ee8be4c6f4555d55e7bee to your computer and use it in GitHub Desktop.
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.minHeap = []
self.maxHeap = []
def addNum(self, num: int) -> None:
if len(self.maxHeap) == 0:
self.maxHeap.append(-num)
return
biggerThanMaxHeap = num > -self.maxHeap[0]
if biggerThanMaxHeap:
heapq.heappush(self.minHeap, num)
else:
heapq.heappush(self.maxHeap, -num)
while len(self.maxHeap) - len(self.minHeap) > 1:
ele = heapq.heappop(self.maxHeap)
heapq.heappush(self.minHeap, -ele)
while len(self.minHeap) - len(self.maxHeap) > 1:
ele = heapq.heappop(self.minHeap)
heapq.heappush(self.maxHeap, -ele)
def findMedian(self) -> float:
if len(self.minHeap) == len(self.maxHeap):
return (self.minHeap[0] - self.maxHeap[0]) / 2
if len(self.minHeap) > len(self.maxHeap):
return self.minHeap[0]
else:
return -self.maxHeap[0]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment