面试题库 › C++ / 后端 › TopK 问题的解法

TopK 问题的解法

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

哪些公司问过

字节跳动20腾讯17百度17美团12拼多多7阿里巴巴6快手5深信服5华为43604蚂蚁集团4微软3

常见岗位:C/C++ 软件开发、Java 后端、C++ 后端、后端开发、Go 后端

答案要点

  1. 排序法:O(n log n),实现最简单,数据量大时不划算
  2. 堆法:找最大 K 个用大小为 K 的小顶堆,比堆顶大就替换;O(n log K),空间 O(K),适合海量和流式数据
  3. 快速选择:基于 partition,平均 O(n)、原地;最坏 O(n²),用随机 pivot 或三数取中缓解
  4. 频率 TopK:哈希表统计频率,再用堆或桶排序取前 K
  5. C++ 可直接用 nth_element(introselect),priority_queue 实现堆

易错点

面试官常见追问

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

相关面试题