购物车中没有产品。
295. 数据流的中位数（困难）
Blind 75 › 295. 数据流的中位数（困难） （第 36 章）
题目
有一个不断加入整数的数据流。请实现 MedianFinder，随时能查询当前已加入的所有数的中位数。
中位数规则：把当前所有数排序后——
- 个数为奇数时，取正中间那个数；
- 个数为偶数时，取中间两个数的平均值。
自造示例：依次执行 addNum(7)、addNum(1)、findMedian()、addNum(9)、findMedian()。
| 操作 | 当前数据（排序） | 结果 |
|---|---|---|
| add(7) | [7] | — |
| add(1) | [1, 7] | — |
| findMedian | [1, 7] | 4.0 |
| add(9) | [1, 7, 9] | — |
| findMedian | [1, 7, 9] | 7.0 |
约束：-105 ≤ num ≤ 105；findMedian 调用前至少有一个数；addNum 与 findMedian 合计最多 5 × 104 次；误差不超过 10-5 即可。
思路
一句话：把数据切成“较小的左半”和“较大的右半”，中位数只由两边的顶端决定。
先想最直白的：用一个有序数组，每次插入时二分找到位置，再把后面元素整体后移。查中位数是 O(1)，但每次插入要 O(n) 搬元素；共 5 × 104 次调用，最坏接近 O(n²)，太慢。
再想偷懒一点的：不排序，查到中位数时再排序。插入 O(1)，查询 O(n log n)，也不够好。
关键观察：中位数只关心中间的一个或两个数，不需要整个数组全排序。只要保证：
- 左半堆存较小的那一半，堆顶是左半最大值；
- 右半堆存较大的那一半，堆顶是右半最小值；
- 左半所有数都 ≤ 右半所有数；
- 两边数量最多差 1（奇数时让左半多一个，方便取数）。
这样中位数不是两个堆顶的平均，就是多出的那个堆顶。堆插入/弹出都是 O(log n)，查询堆顶是 O(1)。
堆的方向不能搞反：左半要大顶堆（能取到较小的那一半里的最大值），右半要小顶堆（能取到较大的那一半里的最小值）。
解法
维护 left（大顶堆，存左半）和 right（小顶堆，存右半）。每次加数分三步：
- 先把新数丢进
left。 - 修正顺序：若
left顶 >right顶，说明有左半元素比右半还大，交换两个堆顶。 - 修正数量：让
left最多比right多 1，否则把多的堆顶搬到另一边。
查询时：left 多一个就返回 left 顶；否则返回两顶平均值。
| 操作 | 左半 left（大顶堆） | 右半 right（小顶堆） | 中位数 |
|---|---|---|---|
| add(7) | [7] | [] | 7 |
| add(1) | [1] | [7] | (1+7)/2 = 4 |
| add(9) | [7, 1]（顶 7） | [9] | 7 |
下图把上面 3 个步骤串成流程，并逐步演示：
C++
class Solution {
public:
MedianFinder() {} void addNum(int num) {
left.push(num); // 先入左半
if (!right.empty() && left.top() > right.top()) { // 修正顺序本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。
还没有评论，来说两句？