TopK，如果k很小，n很大，用什么方法？｜阿里巴巴后端开发面经解析

60 秒回答模板

我会先问清楚是求最大的 k 个还是最小的 k 个，是否要求结果有序，数据是否能放入内存，是否是流式输入，是否允许近似。一般 k 很小、n 很大，不建议全排序，因为全排序 O(n log n) 会计算大量无关顺序。精确求最大 TopK 时，维护一个大小为 k 的小顶堆：先放前 k 个元素，之后每个新元素和堆顶比较，如果更大就替换堆顶并调整；堆顶就是当前 TopK 的门槛。这样整体 O(n log k)、空间 O(k)。如果求最小 TopK，则用大顶堆。若数据在内存数组里且可原地修改，可以用 quickselect 平均 O(n) 找第 k 大分界，但最坏会退化且结果无序。海量数据先按文件块或机器分片做局部 TopK，再合并成全局 TopK；值域小可用计数或桶；如果问的是高频 TopK 且允许误差，可以提 Count-Min Sketch、Space-Saving 等近似算法。

考点 先明确问题边界

主线 避免全排序浪费

易错点 一上来就说排序，忽略 k 很小、n 很大时全排序的 O…

深入解析

先明确问题边界

TopK 不是固定答案，先确认最大还是最小、是否需要排序输出、重复值如何处理、数据在内存还是磁盘、是否流式、是否允许误差。k 很小、n 很大意味着目标是过滤少量候选，而不是获得全部元素的全序关系。这个边界决定了堆、quickselect、桶或分布式方案哪个更合适。

避免全排序浪费

全排序会把 n 个元素全部排成有序序列，复杂度通常是 O(n log n)，但 TopK 只关心前 k 个元素，剩下 n-k 个元素之间的顺序没有价值。当 k 远小于 n 时，全排序为大量无关顺序付费。面试中要说明 TopK 是选择问题，不是排序问题，除非题目额外要求全部有序输出。

最大 TopK 用小顶堆

求最大的 k 个元素时，维护大小为 k 的小顶堆。堆里保存当前扫描过数据中的前 k 大，堆顶是这 k 个候选里最小的那个，也就是进入 TopK 的门槛。新元素不大于堆顶就丢弃；更大就替换堆顶并下沉调整。堆大小始终是 k，特别适合流式和内存受限场景。

最小 TopK 用大顶堆

如果题目改成求最小的 k 个元素，思路完全对称：维护大小为 k 的大顶堆，堆顶是当前 k 个最小候选中最大的那个。新元素更小就替换堆顶，否则丢弃。正确表达是堆顶代表最容易被淘汰的候选，所以最大 TopK 用小顶堆，最小 TopK 用大顶堆。

堆方案的工程价值

堆方案扫描所有元素一次，前 k 个建堆 O(k)，之后每个元素最多触发一次 O(log k) 调整，整体可写成 O(n log k)、空间 O(k)。当 k 很小时，log k 很小，内存占用稳定，不需要保存全部数据。这也是日志流、搜索候选、榜单筛选和在线流式数据里最稳健的方案。

quickselect 平均更快

如果数据都在内存数组里，且允许原地修改，quickselect 是重要补充。它借鉴快排 partition，每次只递归包含第 k 大位置的一侧，不需要把两侧都排好，平均 O(n)、空间接近 O(1)。但最坏可能 O(n^2)，工程上要随机 pivot 或更稳 pivot 策略，而且结果内部不一定有序。

值域受限用计数或桶

如果元素是整数且取值范围不大，计数数组或桶可能比堆更快。先统计每个值出现次数，再从高到低或低到高累计直到取够 k 个，复杂度约 O(n+R)，R 是值域大小。限制是值域必须可控；值域巨大、稀疏或非离散数据时，桶会浪费内存。

海量数据先局部再全局

当 n 大到单机内存放不下时，要先分片。把大文件切成多个块，每块用大小为 k 的堆求局部 TopK，最后汇总所有局部 TopK，再做一次全局 TopK。每片最多贡献 k 个候选，合并阶段数据量从 n 降到 m*k，是单机外部处理和 MapReduce 的通用思路。

javascript

小 k TopK 的最小堆骨架

function topK(nums, k) {
  const heap = [];
  for (const num of nums) {
    if (heap.length < k) {
      heappush(heap, num);
    } else if (num > heap[0]) {
      heapreplace(heap, num);
    }
  }
  return heap.sort((a, b) => b - a);
}

k 很小、n 很大时只维护 k 个候选，整体复杂度是 O(n log k)。
面试现场重点讲清堆顶保存当前 TopK 中最小值，以及何时替换堆顶。

易错点

一上来就说排序，忽略 k 很小、n 很大时全排序的 O(n log n) 浪费。
把最大 TopK 和最小 TopK 的堆方向说反，求最大 k 个却维护大顶堆。
只说用堆，不说明堆大小是 k、堆顶是淘汰门槛，也不分析 O(n log k) 和 O(k)。
把 quickselect 说成一定 O(n)，没有补充平均复杂度、最坏退化和 pivot 随机化。
没有区分结果是否需要有序，忘记说明若要有序只需对 k 个候选再排序。
海量数据仍假设数组在内存里，没提分片、局部 TopK、全局合并或 MapReduce。

面试官追问

求最大的 k 个元素为什么用小顶堆？

堆里只保留当前最有希望成为答案的 k 个元素。求最大 TopK 时，最应该被淘汰的是这 k 个候选里最小的元素，所以让它位于堆顶最方便。新元素只要大于小顶堆堆顶，就能挤进当前 TopK；如果用大顶堆，堆顶是最大值，反而不能快速判断淘汰对象。

堆方案和 quickselect 怎么选？

数据是流式、无法全部放入内存或 k 很小时，优先大小为 k 的堆，因为空间 O(k)，可以边读边处理。数据已经在内存数组里、允许原地修改且更关注平均性能时，可以选 quickselect。但 quickselect 结果无序，最坏会退化，需要随机 pivot 等策略降低风险。

如果要求 TopK 按从大到小输出怎么办？

先用大小为 k 的小顶堆求出最大的 k 个候选，然后只对这 k 个元素排序。总复杂度是 O(n log k + k log k)，通常仍明显优于对 n 个元素全排序。也可以不断弹堆再反转，本质仍是只处理 k 个候选的顺序。

数据量大到内存放不下怎么做？

把数据按文件块或机器分片，每个分片在内存中用堆求局部 TopK，然后把局部结果汇总，再用同样方法求全局 TopK。理由是某个元素如果连所在分片的局部 TopK 都进不了，就不可能成为全局 TopK，可以安全丢弃。

什么时候考虑桶或计数？

当元素是整数、值域较小或能合理分桶时，计数和桶可以把比较问题转成统计问题，复杂度接近 O(n)。但如果值域巨大、稀疏或者元素不是离散整数，桶会占用大量无效内存，反而不如堆稳健。

近似算法适合什么 TopK？

近似算法更适合海量流里的高频 TopK，例如日志关键词、商品点击热点。Count-Min Sketch、Space-Saving、Misra-Gries 用较小内存估计高频项，但会有误差或需要二次校验，不适合必须精确返回数值前 k 大的场景。