LeetCode 面试题 17.20. 连续中值
题目描述
题意分析
设计结构，支持不断加入整数并查询当前中位数。总数为奇数时取有序排列的中间一个数，偶数时取中间两个数的平均值；中位数查询针对已经有数据的状态。
解法：双堆维护有序的左右两半
核心思路
[!blue]
中位数只依赖有序排列的中央边界，不必每次重新排序全部数据。用
small保存较小一半、large保存较大一半，并维持两个条件：较小半区的所有值不大于较大半区的所有值；small的元素数与large相同，或恰好多一个。这样中间位置一定就在堆顶边界上。两个堆都按最小堆实现，但
small保存原值的相反数，因此它的最小值还原符号后，正是较小半区的最大值；large直接保存原值，堆顶就是较大半区的最小值。插入时先把新值加入
small，再把其中最大的原值移到large。这会保留两半的大小关系：若新值很大，它自己被移到右侧；否则移走的是左侧旧最大值，剩余左侧值既不大于它，也不大于原来右侧的值。因此不论新值落在哪个数值范围，移过一次边界后顺序都正确。随后只需修复数量。原来两堆等大时，上述操作会让
large多一个，便把它的最小值移回small；原来small多一个时，操作后恰好等大，无需回移。回移的是右侧最小值，不会破坏两半的大小关系。因此每次插入后仍满足同样的不变量。查询时，若两堆等大，中央两项是
small堆顶恢复符号后的原值与large的堆顶，取其平均；否则small多出的那一项就是中位数。代码先把输入拓宽到long或int64再取负，并用宽类型求两个边界值的和，最后做浮点除法。Go 的两个辅助函数同样维护最小堆：插入把新元素追加到尾部，只沿父链上浮；弹出用末尾元素补根，缩短数组后向较小孩子下沉。除了这条移动路径，其他父子关系原本都合法，因此不需要重新整理整个数组。只有一个元素时，缩短后没有孩子，直接结束下沉。
解题步骤
- 初始化两个空最小堆，
small中的值以相反数形式存放。- 插入新值到
small，再把small对应的最大原值移入large。- 若
large数量更多，将它的最小值移回small。- 查询时根据数量是否相等，返回一个边界值或两个边界值的平均数。
代码实现
class MedianFinder {
private PriorityQueue<Long> small;
private PriorityQueue<Long> large;
public MedianFinder() {
small = new PriorityQueue<>();
large = new PriorityQueue<>();
}
public void addNum(int num) {
// small 用相反数模拟最大堆，堆顶对应较小一半的最大值。
small.offer(-(long) num);
large.offer(-small.poll());
if (large.size() > small.size()) {
small.offer(-large.poll());
}
}
public double findMedian() {
if (small.size() == large.size()) {
return ((-small.peek()) + large.peek()) / 2.0;
}
return -small.peek();
}
}
type MedianFinder struct {
small []int64
large []int64
}
func Constructor() MedianFinder {
return MedianFinder{}
}
func (this *MedianFinder) AddNum(num int) {
// small 保存较小一半的相反数，因此它按最小堆维护。
this.small = pushHeap(this.small, -int64(num))
moved := -this.small[0]
this.small = popHeap(this.small)
this.large = pushHeap(this.large, moved)
if len(this.large) > len(this.small) {
moved = -this.large[0]
this.large = popHeap(this.large)
this.small = pushHeap(this.small, moved)
}
}
func (this *MedianFinder) FindMedian() float64 {
if len(this.small) == len(this.large) {
return float64(-this.small[0]+this.large[0]) / 2.0
}
return float64(-this.small[0])
}
func pushHeap(heap []int64, value int64) []int64 {
heap = append(heap, value)
for child := len(heap) - 1; child > 0; {
parent := (child - 1) / 2
if heap[parent] <= heap[child] {
break
}
heap[parent], heap[child] = heap[child], heap[parent]
child = parent
}
return heap
}
func popHeap(heap []int64) []int64 {
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for parent := 0; ; {
left := parent*2 + 1
if left >= len(heap) {
break
}
child := left
right := left + 1
if right < len(heap) && heap[right] < heap[left] {
child = right
}
if heap[parent] <= heap[child] {
break
}
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
}
return heap
}
复杂度分析
- 时间复杂度：加入一个数均摊 $O(\log(n+1))$，只执行常数次堆操作；查询中位数为 $O(1)$。
- 空间复杂度：$O(n)$，每个已经加入的数保存在其中一个堆中。
关键点总结
[!green]
- 两半的数值顺序保证堆顶是分界值，数量差保证分界恰好位于中央。
small保存相反数，用最小堆取得原值的最大值。- 先移动左侧最大值建立顺序，再按堆大小决定是否回移一次。
易错点总结
[!yellow]
- 读取
small的原值时必须恢复符号，尤其不能把其负数堆顶直接当作中位数。- 只有
large严格更大才回移，等大时回移会破坏数量约定。- 求平均必须做浮点除法，取负和求和也应先在宽类型中完成。
- Go 弹出后应按缩短后的长度判断孩子，并选较小孩子下沉，才能维持最小堆性质。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 480. 滑动窗口中位数 | 困难 | 同样用双堆维护中位数，滑动窗口还需删除过期值或延迟删除。 |
| 703. 数据流中的第 K 大元素 | 简单 | 同样只维护所需排名的边界，原题k固定，可只保留最大的k个元素。 |