目录
- 如何在无序的n个数中找到第k大的数？
- 如何在海量无序的n个数中找到第k大的数？
- 如果k大到连k个数都不能放入内存呢？
最近面试遇到了这个问题，主要考察求职者一定的算法能力及思路，便想将这个问题及其变种问题系统的总结一下，将我个人的解决思路给大家分享一下。
如何在无序的n个数中找到第k大的数？
首先回顾一下这个问题的最初版本，即非海量数据的情况下。
基础做法：
- 使用最小堆： 维护一个大小为 k 的最小堆，遍历数组，将元素加入堆中，如果堆的大小超过 k，则移除堆顶元素。最终堆顶元素即为第 k 大的元素。时间复杂度为 O(nlogk)。
- 完全排序： 将数组排序后直接取第 k 个元素，但时间复杂度较高，为 O(nlogn)。
要在无序的 n 个数中高效地找出第 k 大的元素，可以使用 快速选择算法（Quickselect）。这是一个平均时间复杂度为 O(n) 的算法，而且是原地算法，不需要额外的存储空间 ，专门用于在无序数组中寻找第 k 大或第 k 小的元素。
快速选择算法的基本思想：
-
1、选择一个枢纽元（Pivot）： 通常随机选择数组中的一个元素作为枢纽元。
-
2、划分数组： 通过一次遍历，将数组分成两部分：
-
- 左侧的元素都大于等于枢纽元（如果寻找第 k 大的元素）。
-
- 右侧的元素都小于枢纽元。
-
3、递归选择：
-
- 如果左侧部分的元素数量等于 k，那么左侧部分的最后一个元素即为第 k 大的元素。
-
- 如果左侧部分的元素数量大于 k，在左侧部分递归执行上述步骤。
-
- 如果左侧部分的元素数量小于 k，在右侧部分寻找第 k−左侧元素数量 大的元素。
如何在海量无序的n个数中找到第k大的数？
要在无法一次性将所有数据读入内存的情况下找到第 k 大的元素，可以采用分块处理的方法：
使用大小为 k 的最小堆（Min-Heap）：
-
1、初始化最小堆： 创建一个容量为 k 的最小堆，用于存储当前找到的前 k 大的元素。
-
2、分批读取数据： 由于内存限制，我们不能一次性读取所有数据。因此，将数据分成可以容纳于内存的小批次进行处理。
-
3、处理每个元素。对于每个读取的元素 x：
如果最小堆的大小小于 k，则直接将 x 插入堆中。
如果堆已满且 x 大于堆顶元素（即当前堆中最小的元素），则将堆顶元素替换为 x，并对堆进行调整以维持最小堆的性质。
如果 x 小于或等于堆顶元素，忽略它，因为它不可能是前 k 大的元素。 -
4、迭代处理： 重复步骤2和3，直到所有数据都被处理完。
-
5、获取结果： 在所有数据处理完毕后，最小堆中的元素就是数据集中的前 k 大元素，堆顶元素即第 k 大的元素。
优点：内存效率高： 由于堆的大小固定为 k，只需在内存中维护 k 个元素，适用于超大规模的数据集。
时间效率高： 每次插入或替换堆顶元素的操作时间复杂度为 O(logk)，总体时间复杂度为 O(nlogk)。
优化方案，多线程并行处理：
为每个数据块启动一个线程（或进程），在各自的线程中执行以下操作：
局部求解： 使用大小为 k 的最小堆，在自己的数据块中找到该块的前 k 大元素。
合并局部结果：在所有线程完成后，将每个线程得到的前 k 大元素进行合并，得到全局的前 k 大元素。具体的合并方法如下：
汇总所有最小堆： 将所有线程返回的最小堆中的元素汇总成一个列表，总大小为 k×s（其中 s 为线程数）。
再次构建最小堆： 在合并后的列表上再次构建一个大小为 k 的最小堆，找出全局的前 k 大元素。
如果k大到连k个数都不能放入内存呢？
如果n和k都很大，即k个数都不能被一次性读入到内存，即假设有一万个数，k是400，但是内存只能存放100个数(假设)，这种情况下，怎么样高效找出第k大的元素呢？
可以采用 多次遍历的数据分桶或称桶排序 的方法。以下是具体步骤：
- 1、第一次遍历（计算最小值和最大值）：由于内存只能容纳 100 个数，我们无法一次性读取所有数据。我们可以顺序读取数据，在此过程中，更新并记录整个数据集的最小值（min）和最大值（max）。
- 2、建立桶的范围：根据第一次遍历得到的 min 和 max，将整个数据范围划分为 B 个桶（这里 B≤100 以适应内存限制）。每个桶代表一个数值区间，区间大小为 (max−min)/B。
- 3、第二次遍历（统计每个桶中的元素数量）：再次顺序读取数据，根据每个数的值，确定其所属的桶，并增加该桶的计数器。在遍历过程中，仅需在内存中维护一个大小为 B 的计数数组。
- 4、确定包含第 k 大元素的桶：从最大值所在的桶开始，累加每个桶的元素数量。当累加的元素数量达到或超过 k 时，记录当前桶为目标桶。这意味着第 k 大的元素必定在这个桶的范围内。
- 5、缩小范围并递归处理：如果目标桶中的元素数量仍然超过内存容量，则对该桶再次进行步骤 2 到步骤 4 的处理。
在新的范围内，将目标桶进一步划分为更细的桶，重复上述过程。这个过程可能需要多次迭代，每次都将范围缩小，直到目标桶内的元素数量可以被内存容纳。 - 6、在内存中找出第 k 大元素：当目标桶内的元素数量小于或等于内存容量时，将这些元素全部读入内存。对这些元素进行排序或使用适当的选择算法，根据已经遍历过的元素数量，便可在直接内存中找出第 k 大元素。
