Top-K问题的常见求解思路有哪些？

## 作用 Top-K 问题用于从 n 个元素中找出最大的 k 个或最小的 k 个元素，常见于面试题和海量数据处理场景。常见求解思路主要有以下三类： - **全局排序** - 先对整个数组排序，再取前 k 个元素。 - 使用快排、归并排序、堆排序时，时间复杂度通常为 `O(n log n)`。 - 使用冒泡、插入、选择排序时，时间复杂度通常为 `O(n²)`。 - 优点是简单直观；缺点是做了大量不必要的排序工作，因为只需要前 k 个元素，却排好了全部元素。 - 适合数据量较小的场景；数据量超过内存容量时，还可能产生较大的磁盘 IO 开销。 - **冒泡式部分排序** - 利用冒泡排序每轮确定一个最大值的特点，只执行 k 轮冒泡，即可得到最大的 k 个数。 - 时间复杂度为 `O(n·k)`。 - 相比全局排序减少了一部分计算，但当 k 接近 n 时，会退化为 `O(n²)`。 - 如果维护大小为 k 的数组并进行插入排序，还需要额外付出查找插入位置和移动数组元素的成本。 - **堆方案** - 这是 Top-K 问题的经典解法，核心是用大小为 k 的堆维护当前最优的 k 个元素。 - 求最大的 k 个数：使用**小根堆**。 - 求最小的 k 个数：使用**大根堆**。 - 时间复杂度为 `O(n log k)`，空间复杂度为 `O(k)`。 - 不需要让最终的 k 个元素内部有序，适合大规模数据处理。 ## 原理 ### 1. 堆的基本性质 - 堆也叫优先队列、二叉堆，逻辑上是一棵完全二叉树，物理上通常用数组存储。 - **大根堆**：堆顶是堆中的最大值，每个父节点都大于或等于子节点。 - **小根堆**：堆顶是堆中的最小值，每个父节点都小于或等于子节点。 - 使用从 0 开始的数组下标时： - 节点 `i` 的父节点下标为 `(i - 1) / 2`； - 左子节点下标为 `2i + 1`； - 右子节点下标为 `2i + 2`。 ### 2. 求 Top-K 大时为什么用小根堆 以求最大的 k 个数为例： 1. 先取前 k 个元素，建立大小为 k 的小根堆。 2. 小根堆的堆顶是当前 k 个元素中的最小值，也就是进入“前 k 名”的门槛。 3. 遍历剩余元素： - 如果当前元素大于堆顶，说明它有资格进入前 k 名； - 删除堆顶，将当前元素插入堆中； - 调整堆，继续保持小根堆性质。 4. 遍历结束后，堆中保存的就是全局最大的 k 个元素，堆顶就是第 k 大的数。 不能使用大根堆求 Top-K 大，是因为大根堆堆顶表示当前 k 个元素中的最大值，无法快速知道应当淘汰的最小值；而小根堆可以用 `O(1)` 时间取得当前最小值。 ### 3. 求 Top-K 小时为什么用大根堆 以求最小的 k 个数为例，逻辑正好相反： 1. 用前 k 个元素建立大小为 k 的大根堆。 2. 大根堆堆顶是当前 k 个元素中的最大值，即最小 k 个元素的门槛。 3. 遍历剩余元素时，如果当前元素小于堆顶，就删除堆顶并插入当前元素。 4. 遍历结束后，堆中保存的就是全局最小的 k 个元素。 ### 4. 复杂度对比 - 全局排序：通常为 `O(n log n)`，简单但冗余。 - k 轮部分排序：`O(n·k)`，k 较大时性能较差。 - 大小为 k 的堆：`O(n log k)` 时间、`O(k)` 空间，是更适合 Top-K 的经典方案。

## 作用 Top-K 用于从大规模数据中找出最大的 K 个、最小的 K 个或出现次数最多的 K 个元素。选择方案时要结合： - 数据量级是否能全部放入内存； - 数据类型是 `int`、字符串还是带频次的对象； - K 的大小以及结果是否要求有序； - 是一次查询还是反复查询； - 主要矛盾是时间复杂度、空间复杂度，还是外部存储和分布式处理。 ## 常见思路 ### 1. 堆排序法 适合海量数据中在线维护 Top-K，尤其适合 K 较小、数据不能一次性全部加载的场景。 - 求最大的 K 个：维护一个大小为 K 的**小顶堆**。 - 新元素大于堆顶时，弹出堆顶并插入新元素； - 否则直接跳过； - 遍历结束后，堆中就是最大的 K 个元素。 - 求最小的 K 个：维护一个大小为 K 的**大顶堆**。 - 时间复杂度：`O(n log k)`。 - 空间复杂度：`O(k)`。 - 如果要求结果有序，最后再对堆中的 K 个元素排序。 - 也可以扩展到多个有序数组：先把每个数组的候选极值放入堆，每次弹出堆顶后补充同一数组中的下一个元素。 ### 2. 类快排划分法 借鉴快速排序的 `partition`，但不排序整个数组，只继续划分包含目标位置的一侧。 - 每次选择 pivot，将数组划分为左右两部分； - 如果 pivot 位置已经把前 K 个或后 K 个元素区分出来，就不必再处理另一侧； - 求最大的 K 个数时，可以转换为定位第 `n-k` 小的位置，右侧 K 个元素即为答案； - 最优时间复杂度可达到 `O(n)`，平均情况下通常按 `O(n log n)` 量级理解； - 找出的 K 个元素内部默认无序，需要时额外排序。 这种方法通常要求数据可以放入内存，更适合一次查询。 ### 3. Bitmap 位图法 用一个二进制位表示某个整数是否出现，以位换空间。 - 对有明确取值范围且不重复的整数，可以把对应位置标记为 1； - 从高位到低位扫描，即可找到最大的 K 个数； - 对连续出现的区间，还可以结合跳表等结构记录“起始位置 + 连续长度”，进一步压缩空间； - 适合不重复、范围可接受的整数； - 不适合值域极度稀疏或无法合理映射的数据； - 如果存在重复数据，可以配合计数或 Hash 结构处理。 ### 4. Hash 法 适合先统计频次，再求“出现次数最多的 K 个”这类问题。 - 先用 Hash 表统计每个元素的出现次数； - 再遍历 Hash 表，用大小为 K 的小顶堆按频次维护 Top-K； - 常见于高频词、热门查询串、热点用户等场景； - 堆处理阶段的时间复杂度通常为 `O(n log k)`。 ### 5. 字典树（Trie） 适合字符串类型数据，尤其是查询词、高频前缀等场景。 - 可用字典树保存字符串及出现次数； - 在前缀匹配、词频统计方面比普通字符串比较更有结构优势； - 得到频次或候选集合后，仍可结合堆得到 Top-K； - 适合字符串重复较多、存在前缀查询需求的场景。 ### 6. 混合查询方案 真实场景通常不是单一结构就能解决，需要根据约束组合多种方法： - Hash 统计频次 + 小顶堆求热门 Top-K； - Bitmap 去重或标记整数 + 跳表压缩连续区间； - Trie 处理字符串前缀和词频 + 堆维护排名； - 多个有序局部结果 + 堆做全局归并； - 数据无法放入内存时，可先分治、分片或外存处理，再合并每片的 Top-K。 ## 选型总结 - **数据量大、K 小、流式处理**：优先考虑大小为 K 的堆。 - **数据可放入内存、追求一次查询效率**：可以考虑类快排划分。 - **一定范围内的不重复整数**：适合 Bitmap。 - **按出现次数排名**：先用 Hash 计数，再用堆求 Top-K。 - **字符串、前缀和词频问题**：可考虑字典树。 - **复杂工程场景**：通常采用 Hash、Bitmap、Trie、堆、分治和多路归并的组合方案。