LeetCode 295. [Python] Find Median from Data Stream
原题链接
困难
作者:
徐辰潇
,
2021-08-28 00:30:29
,
所有人可见
,
阅读 353
class MedianFinder:
#TC: O(log len(heap) for each add operation
#SC: O(len(heap))
#Keep two heap to maintain the first half and next half of the input data
def __init__(self):
"""
initialize your data structure here.
"""
self.above = []
self.below = []
def addNum(self, num: int) -> None:
if len(self.below) == 0 or -self.below[0] > num:
heapq.heappush(self.below, -num)
else:
heapq.heappush(self.above, num)
if len(self.below) >= len(self.above) + 2:
ele = -self.below[0]
heapq.heappop(self.below)
heapq.heappush(self.above, ele)
if len(self.above) >= len(self.below) + 1:
ele = self.above[0]
heapq.heappop(self.above)
heapq.heappush(self.below, -ele)
def findMedian(self) -> float:
if len(self.below) == len(self.above) + 1:
return -self.below[0]
elif len(self.below) == len(self.above):
return (-self.below[0] + self.above[0]) / 2.0
else:
return -1
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()