1. 小规模 / 一次性批量数据
- 排序 + 截取
- 把所有数据整体排序（复杂度 O(N log N)），然后取前 K 个。
- 适合一次性查询、不需要频繁更新的情况。
2. 大规模数据 / K 远小于 N
- 堆（Heap）
- 维护一个大小为 K 的最小堆（找最大 K）或最大堆（找最小 K）。
- 插入每个元素时：
- 若堆未满 → 直接加入；
- 若堆满且新元素更优 → 替换堆顶。
- 复杂度 O(N log K)，比全量排序高效。
- 常用于实时排行榜。
为什么是小顶堆？
因为我们希望淘汰那些相对较小的元素。根据小顶堆的定义，堆顶始终是当前 K 个元素中的最小值。当我们遇到一个比这个最小值更大的新元素时，它就有资格进入前 K 名。这时，我们可以用新元素替换掉当前最小的元素，并重新调整堆。这样，堆中始终保持着最大的 K 个元素。
如果我们要找最小的 K 个元素，则使用同样的方法，但构建一个大顶堆。
除了堆，还有一些其他方法可以解决 Top-K 问题，但它们通常在特定场景下使用，或者效率不如堆。
- 快速选择（Quickselect）：
- 这是一种基于快速排序（Quicksort）的分治算法，但只处理一边的分区。
- 它的平均时间复杂度是 O(N)，比堆的 O(N log K) 更好，但在最坏情况下可能退化到 O(N^2)。
- 它通常用于离线（所有数据一次性可用）且不需要持续维护的场景。
- 实现起来比堆复杂，且不如堆稳定。
- 计数排序或桶排序（Counting Sort / Bucket Sort）：
- 如果数据的范围有限且相对较小，可以使用这些线性时间复杂度的排序算法。
- 它们的时间复杂度是 O(N + M)，其中 M 是数据范围。
- 这种方法有很强的局限性，不适用于数据范围非常大或数据类型为浮点数的情况。
3. 分布式/大数据场景
- MapReduce / 分布式 Top-K （分治的思想）
- 每个分片先算出局部 Top-K；
- 汇总后再取全局 Top-K。
- 大幅减少通信和内存压力。
4.拓展延伸
1. 从十亿数据中找到出现次数最多的十个数字
用hash树记录每个数字出现的频率，转化为在各个数字的频率中找到Top K的问题。
2. 从十亿数据中找到升序的第七亿个数
2.1 快速排序
- step1：以数组最后一个元素作为基准值，将数据partition为
[left,mid-1]和[mid,right]两个区间，其中[left,mid-1]的数都小于base值，[mid,right]都大于等于base值 - step2：计算
[mid, right]数组长度L：- 如果L等于三亿，那么
[left,mid-1]中的七亿个数字小于[mid,right]中的三亿个数字，只需要在[left,mid-1]中找到最大值即可 - 如果L大于三亿，则将问题转化为在
[mid, right]中找到第（L-三亿）个数 - 如果L小于三亿则问题还是在
[left,mid-1]中找到第七亿大的数
- 如果L等于三亿，那么
在step2中，如果数据量级足够小则可以直接进行排序得到答案。
2.2 桶排序
假如数据的范围是有限的（有最大值和最小值）且较均匀分布，那么使用桶排序可以进一步提升效率：
- step1：获取数据的max和min
- step2：将所有的n份数据分到m个文件中，同时记录每份子文件中的数据量
- step3：从小到大累加文件数据量，找到第七亿个数所在的文件，记录前面文件的总数据量count
- step4：将问题转化为在第七亿个数所在的文件中寻找第（七亿-count）个数
在step4中，如果内存足够存放所有数据，可以直接排序获取第七亿个数字。