面试题库 › C++ / 后端 › 数据流的中位数(支持删除)

数据流的中位数(支持删除)

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:TopK与海量数据

哪些公司问过

字节跳动1

常见岗位:游戏服务端

答案要点

  1. 大顶堆存较小一半、小顶堆存较大一半,中位数取自堆顶
  2. 删除采用延迟删除:哈希表记录每个值待删除次数
  3. 根据与大顶堆堆顶比较判断待删元素所在的一半,更新有效计数
  4. 访问堆顶前先清理已标记删除的元素
  5. 按有效元素数平衡两堆,大小差不超过 1,均摊 O(log n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题