面试题库 › C++ / 后端 › 数据流的中位数(大根堆加小根堆)

数据流的中位数(大根堆加小根堆)

难度 ★★★在 5 场真实面经中被问到 方向:C++ / 后端考点:栈与队列

哪些公司问过

腾讯1亚马逊13601米哈游1网易互娱1

常见岗位:游戏服务端、C++ 后端、软件开发、C/C++ 软件开发

答案要点

  1. 大根堆存较小的一半,小根堆存较大的一半
  2. 保持两堆大小相差不超过 1,通常大根堆不少于小根堆
  3. 插入时经大根堆再转移到小根堆,并平衡大小,保证两堆的大小关系
  4. 查询:大小不等取大根堆堆顶,相等取两个堆顶的平均值
  5. 插入 O(log n),查询 O(1),空间 O(n);数据范围有限时可用计数数组

易错点

面试官常见追问

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

相关面试题