数据流的中位数(支持删除)
哪些公司问过
答案要点
- 大顶堆存较小一半、小顶堆存较大一半,中位数取自堆顶
- 删除采用延迟删除:哈希表记录每个值待删除次数
- 根据与大顶堆堆顶比较判断待删元素所在的一半,更新有效计数
- 访问堆顶前先清理已标记删除的元素
- 按有效元素数平衡两堆,大小差不超过 1,均摊 O(log n)
易错点
- 用堆的实际大小判断平衡,忽略待删除元素
- 只在弹出时清理,取中位数前没清理堆顶
- 删除时用 erase(value) 把 multiset 中所有相同值都删掉
面试官常见追问
- 为什么要维护有效元素数?
- 不用延迟删除有什么方案?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。