思路:维护一个大顶堆和一个小顶堆;
import heapq
class MedianFinder(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.len = 0
self.minheap = []
self.maxheap = []
def addNum(self, num):
"""
:type num: int
:rtype: None
"""
self.len += 1
heapq.heappush(self.maxheap, -heapq.heappushpop(self.minheap, num))
if len(self.maxheap) > len(self.minheap):
heapq.heappush(self.minheap, -heapq.heappop(self.maxheap))
def findMedian(self):
"""
:rtype: float
"""
if self.len & 1 == 0:
return (self.minheap[0] - self.maxheap[0]) / 2.0
return self.minheap[0]
m = MedianFinder()
m.addNum(2)
print(m.maxheap, m.minheap)
m.addNum(3)
print(m.maxheap, m.minheap)
print(m.findMedian())
m.addNum(4)
print(m.maxheap, m.minheap)
print(m.findMedian())
[] [2] [-2] [3] 2.5 [-2] [3, 4] 3