IT 面试题库

Top K 问题(最大 K 个数)有哪些解法?

高级简答题算法工程师大数据开发工程师TopK堆算法

题目

对比排序、最小堆、快速选择。

参考答案

内容深度:基础 · 无代码示例 · 来源:种子题库 · 未复核 · 89 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
  1. 全排序 O(n log n):简单但浪费(只需 K 个)。
  2. 最小堆(优先队列) O(n log K):维护大小为 K 的最小堆,遍历时比堆顶大就替换,最终堆内即 Top K。适合流式/海量数据。
  3. 快速选择(BFPRT) 平均 O(n):类似快排 partition,每次只递归含第 K 大的那一侧,不全局排序。
  4. 计数/桶排序:数据范围有限时 O(n)。

工程选型:内存够且需稳定 → 堆;追求理论最优 → 快速选择;分布式 → MapReduce 分桶。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题