数据流的中位数 图解题解
这道题到底在问什么
- 依次加入
- 5, 3, 8, 1
- 每次中位数
- 5 → 4 → 5 → 4
最优解：一步一步想明白
- 3数一直在来，每问一次就重新排序，查得越频繁越崩。我们要的是「随时 O(1) 拿到中位数」，又不想每次重排——这正是要优化掉的浪费。
- 4转折：中位数只跟「最中间那一两个数」有关，何必排好全部？用大顶堆 small 装较小一半（堆顶=这半的最大值）、小顶堆 large 装较大一半（堆顶=那半的最小值）。中位数永远卡在这两个堆顶上，拿它 O(1)。
- 5维持两条规则：① small 里每个数 ≤ large 里每个数；② 本实现约定 small 的个数必须等于 large、或恰好比它多 1（即 len(small) − len(large) ∈ {0, 1}）。所以「small 多 2」或「large 比 small 多」都算失衡，要挪一个堆顶过去。奇数个时中位数 = small 堆顶；偶数个时 = 两堆顶平均。下面逐个加 5、3、8、1。
- 6small=[5], large=[]第一个数 5，放进左边大顶堆 small。两堆个数差 1，已平衡，不用挪。
- 7奇数个 → 中位数 = 5一共 1 个数，奇数，中位数 = 数多的那个堆顶 = small 顶 5。
- 8small=[3,5], large=[]加入 3：它比 small 顶 5 小，进左堆。但左堆一下多了 2 个、右堆空着——失衡了，下一步要调。
- 9中位数 = (3+5)/2 = 4平衡：把 small 堆顶 5 挪到 large。现在左 [3]、右 [5] 各一个。偶数个，中位数 = 两堆顶平均 = (3+5)/2 = 4。
- 10small=[3], large=[5,8]加入 8：比 large 顶 5 大，进右堆。这回右堆多了 1 个，又失衡——往多的一边的反方向挪。
- 11奇数个 → 中位数 = 5平衡：把 large 堆顶（最小的）5 挪回 small。左 [3,5]、右 [8]。奇数个，中位数 = 数多的 small 顶 5。
- 12small=[1,3,5], large=[8]加入 1：比 small 顶小，进左堆。左堆涨到 3 个，比右堆多 2——再调一次。
- 13中位数 = (3+5)/2 = 4平衡：small 顶 5 挪到 large。左 [1,3]、右 [5,8]。四个数排序是 1,3,5,8，中间两个 3、5，中位数 = (3+5)/2 = 4。全程没有重排，每步只挪一个堆顶。
- 16「动态求中位数 / 求第 K 大」的经典结构：一个大顶堆 + 一个小顶堆对顶，维持大小平衡，中位数永远在两个堆顶之间。
⚠️ 容易写错的地方
✗ 错：大顶堆、小顶堆装反（small 装大的）
✓ 对：small 装较小一半、large 装较大一半
装反了堆顶就不是中间值，中位数全错
✗ 错：只入堆不平衡
✓ 对：每次 addNum 后检查并调平两堆大小
不平衡的话「中间」会偏到一边，堆顶不再是中位数
✗ 错：Python 直接用 heapq 当大顶堆
✓ 对：存相反数模拟大顶堆
heapq 只有小顶堆，装较小一半要靠存负数来「翻转」
完整代码（Python / C++ / Java）
Python
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # 大顶堆(存负数模拟)，装较小一半
self.large = [] # 小顶堆，装较大一半
def addNum(self, num):
heapq.heappush(self.small, -num) # 先进大顶堆
heapq.heappush(self.large, -heapq.heappop(self.small)) # 顶给小顶堆
if len(self.large) > len(self.small): # 维持 small ≥ large
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0] # 奇数 → 数多的 small 堆顶
return (-self.small[0] + self.large[0]) / 2 # 偶数 → 两堆顶平均C++
class MedianFinder {
priority_queue<int> small; // 大顶堆:较小一半
priority_queue<int, vector<int>, greater<int>> large; // 小顶堆:较大一半
public:
void addNum(int num) {
small.push(num);
large.push(small.top()); small.pop(); // 顶给小顶堆
if (large.size() > small.size()) { // 维持 small ≥ large
small.push(large.top()); large.pop();
}
}
double findMedian() {
if (small.size() > large.size()) return small.top();
return (small.top() + large.top()) / 2.0;
}
};Java
class MedianFinder {
PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder()); // 大顶堆
PriorityQueue<Integer> large = new PriorityQueue<>(); // 小顶堆
public void addNum(int num) {
small.offer(num);
large.offer(small.poll()); // 顶给小顶堆
if (large.size() > small.size()) // 维持 small ≥ large
small.offer(large.poll());
}
public double findMedian() {
if (small.size() > large.size()) return small.peek();
return (small.peek() + large.peek()) / 2.0;
}
}套路模板 · 对顶堆（背下来）
small = [] # 大顶堆(负数)，装较小一半
large = [] # 小顶堆，装较大一半
# 加数：保证 small 的所有数 <= large 的所有数
# 平衡：两堆大小差 <= 1
# 中位数：奇数取多的那堆顶，偶数取两堆顶平均复杂度
时间复杂度
O(log n)
addNum 每次堆插入/弹出 O(log n)；findMedian 直接读两个堆顶 O(1)
空间复杂度
O(n)
两个堆合起来存下所有 n 个数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数据流的中位数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
对顶堆：大顶堆 small 装较小一半、小顶堆 large 装较大一半，维持两堆大小差 ≤ 1。addNum 先入 small、把 small 顶挪给 large、若 large 更大再挪回，O(log n)。findMedian 奇数取 small 顶、偶数取两堆顶平均，O(1)。
为什么不用「有序数组 + 二分插入」？+
有序数组虽能 O(log n) 二分定位，但插入要搬移元素 O(n)。对顶堆把插入降到 O(log n)、取中位数 O(1)，更适合数据流不断加入的场景。
如果数值范围很小(如 0~100)，有没有更快的？+
可以用计数桶(bucket)：addNum 时对应桶 +1，O(1)；findMedian 时从小到大累加桶计数找到中位位置。值域固定时常数更优。
复杂度多少？+
addNum O(log n)(堆操作)，findMedian O(1)(读堆顶)，空间 O(n) 存所有数。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。