295. Find Median from Data Stream
兩個(gè)heap解決問題，比find window median要容易些
class MedianFinder(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.left = []
self.right = []
def addNum(self, num):
"""
:type num: int
:rtype: void
"""
right = self.right
left = self.left
if not left or num <= -left[0]:
heapq.heappush(left, -num)
else:
heapq.heappush(right, num)
self.balance(left, right)
def findMedian(self):
"""
:rtype: float
"""
right = self.right
left = self.left
if len(left) == len(right):
return (right[0] - left[0])*1.0/2
else:
return -left[0]
def balance(self, left, right):
if len(right) > len(left):
val = heapq.heappop(right)
heapq.heappush(left, -val)
elif len(left) - 1 > len(right):
val = heapq.heappop(left)
heapq.heappush(right, -val)
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
