数据流的中位数
Find Median from Data Stream
本机进度仅保存在当前浏览器
题目描述
中位数是有序整数列表中的中间值。实现 MedianFinder 类：addNum(num) 从数据流中添加一个整数；findMedian() 返回目前所有元素的中位数。两方法都要求尽量高效。
示例：依次 addNum(1)、addNum(2)，findMedian() 返回 1.5；addNum(3) 后 findMedian() 返回 2。
解题思路
- 双堆结构：大顶堆 small 存较小的一半，小顶堆 large 存较大的一半，两堆大小差不超过 1。
- 中位数：两堆等大时取堆顶平均；不等时取较大堆的堆顶。
- 插入规则：新数先进 large，再把 large 堆顶移到 small 保持有序划分；按两堆大小交替平衡。每次 O(log n)。
- 查询 O(1)——双堆把"动态有序集合取中位数"的成本压到了插入侧。
参考实现
查看参考实现Python · 建议先自行作答
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # 大顶堆（存负值）
self.large = [] # 小顶堆
def addNum(self, num):
# 先进 large，再搬运堆顶保持划分有序
heapq.heappush(self.large, num)
heapq.heappush(self.small, -heapq.heappop(self.large))
# 平衡两堆大小：small 允许多一个
if len(self.small) > len(self.large):
heapq.heappush(self.large, -heapq.heappop(self.small))
def findMedian(self):
if len(self.large) > len(self.small):
return float(self.large[0])
return (self.large[0] - self.small[0]) / 2