LeetCode 295. 数据流的中位数
题目描述
题意分析
设计一个支持不断插入整数的数据结构，并能随时返回当前所有已插入元素的中位数。若把这些元素排序，数量为奇数时中位数是正中间的一项，数量为偶数时是中间两项的平均值。
每次插入都增加一次出现，重复值也要计入总数；允许负数，平均值也可能带小数。每次查询针对当时已经插入的数据，而不是最终的整条数据流。题目保证调用查询前至少有一个元素，不需要定义空数据流的中位数。
解法：双堆维护中位数
核心思路
[!blue]
中位数只由有序数据中间的一项或两项决定，不需要让所有元素完全有序。把数据分成较小的一半和较大的一半：最大堆
small保存较小部分，让它的堆顶暴露左半最大值；最小堆large保存较大部分，让它的堆顶暴露右半最小值。始终维护两条条件：
small中任意值不大于large中任意值；small的数量与large相同，或只多一个。于是总数为奇数时，正中间的值就是small堆顶；总数为偶数时，两个中间值就是两个堆顶。插入新数时，若
small为空或新数不大于它的堆顶，就放入small，否则放入large。这样不会破坏两部分的大小分界，但可能使数量失衡。small多出两个时，把它的最大值移到large；large比small多时，把它的最小值移到small。移动的是两部分之间的边界元素，因此数量恢复后，大小分界仍然成立。每次只新增一个数，而此前两堆已经平衡，所以最多移动一个堆顶即可恢复所需数量关系，不需要循环重平衡。
Go 的实现复用最小堆，通过保存相反数来表示
small：原值越大，相反数越小。比较新值、跨堆移动以及读取中位数时，都需要正确还原或添加负号。求两个堆顶平均值时先转为浮点数再相加，保留小数部分并避免整数加法先溢出。
解题步骤
- 初始化空的
small最大堆与large最小堆。- 新数不大于
small的最大值时放入small，否则放入large；首个数直接进入small。- 若
small比large多两个元素，将其堆顶移到large；若large更多，将其堆顶移到small。- 查询时，两堆等大返回堆顶的浮点平均值；否则返回
small的堆顶原值。
代码实现
class MedianFinder {
private final PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
private final PriorityQueue<Integer> large = new PriorityQueue<>();
public MedianFinder() {}
public void addNum(int num) {
if (small.isEmpty() || num <= small.peek()) {
small.offer(num);
} else {
large.offer(num);
}
// 保存较小一半的堆最多多一个元素，移动堆顶维持大小平衡。
if (small.size() > large.size() + 1) {
large.offer(small.poll());
} else if (large.size() > small.size()) {
small.offer(large.poll());
}
}
public double findMedian() {
if (small.size() == large.size()) {
// 相加前先转浮点，避免两端整数直接相加溢出。
return (small.peek() + (double) large.peek()) / 2;
}
return small.peek();
}
}
import "container/heap"
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
last := len(old) - 1
x := old[last]
*h = old[:last]
return x
}
type MedianFinder struct {
// 保存相反数，用最小堆模拟最大堆
small IntHeap
large IntHeap
}
func Constructor() MedianFinder {
return MedianFinder{}
}
func (this *MedianFinder) AddNum(num int) {
if len(this.small) == 0 || num <= -this.small[0] {
heap.Push(&this.small, -num)
} else {
heap.Push(&this.large, num)
}
// 较小一半最多多一个元素，转移时还要恢复或添加相反数符号。
if len(this.small) > len(this.large)+1 {
heap.Push(&this.large, -heap.Pop(&this.small).(int))
} else if len(this.large) > len(this.small) {
heap.Push(&this.small, -heap.Pop(&this.large).(int))
}
}
func (this *MedianFinder) FindMedian() float64 {
if len(this.small) == len(this.large) {
// 先还原较小一半的最大值，再用浮点数计算两个中间值平均数。
return (float64(-this.small[0]) + float64(this.large[0])) / 2
}
return float64(-this.small[0])
}
复杂度分析
- 时间复杂度：插入为 $O(\log n)$，进行一次入堆以及至多一次跨堆转移；查询为 $O(1)$，只读取一个或两个堆顶。
n为当前元素总数。- 空间复杂度：$O(n)$，两个堆共同保存全部已插入元素，每次出现都需要保留。
关键点总结
[!green]
- 左半取最大值、右半取最小值，让两个堆顶正好朝向中位分界。
- 数值分界与数量平衡必须同时成立，单独满足任何一条都不够。
- 插入后只移动边界极值，在调整数量的同时保留正确分区。
进阶：利用取值分布优化
全部数值在 0 到 100 之间
若全部输入都在
[0, 100]，可以使用长度为101的频次数组count，记录每个整数的出现次数，并维护总数total。插入时只执行对应计数加一，不必使用堆。按一基排名，两个中间位置分别为
(total + 1) / 2和(total + 2) / 2，这里使用整数除法。总数为奇数时它们相同，为偶数时它们相邻。从数值0到100累加频次，累计数量首次达到对应排名时，该数值就是所求的中间项；最后求两项的浮点平均值。插入为 $O(1)$，查询最多扫描
101个计数，空间固定为 $O(101)$。这个优化依赖取值范围固定且很小，不能直接套在一般整数流上。
99% 的数值在 0 到 100 之间
若每次查询时，当前已插入数据中至少
99%位于[0, 100]，那么超过一半的数据都在这个区间，两个中位排名必定位于区间内。除101个频次外，只需额外记录小于0的数量below和大于100的数量，并将所有插入都计入total。先按全部数据计算两个中间排名，再分别减去
below，就是它们在区间内的排名。随后像前一种情况一样扫描频次即可。区间外的具体值不会成为本次中位数，但小于区间的元素会把区间内所有排名向后推，所以不能忽略它们的数量。若题目只保证最终全部数据满足这个比例，流的早期却不一定满足，那么早期中位数可能位于区间外。此时只保留外围数量会丢失计算答案所需的数值，不能直接丢弃这些值；继续使用前面的双堆方案即可处理任意插入过程。两种分布条件来自官方进阶问题，使用优化前需要区分当前查询前提与最终总体前提。
易错点总结
[!yellow]
- 只看两堆大小决定新数放哪边，可能使左半出现大于右半的值，堆顶便不再代表中间位置。
- 两个堆方向写反，会暴露最外侧的极值，而不是中间分界。
- 强行要求两堆永远一样大，无法处理奇数个元素；本实现让多出的一个固定留在
small。- 偶数情况使用整数除法，或者相加后才转换为浮点数，会丢失小数或让整数中间结果溢出。
- Go 的
small存相反数，比较、跨堆移动和查询任一步漏掉符号转换都会破坏结果。- 分布优化只有在对应范围或比例条件成立时才能使用，不能把最终数据的比例保证当成流中每次查询的保证。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 480. 滑动窗口中位数 | 困难 | 中位数维护相同，滑动窗口还需删除过期值或做延迟删除。 |
| 703. 数据流中的第 K 大元素 | 简单 | 同样维护排名边界，原题k固定可只保留k个最大值，本题中间位置随总数变化。 |