转载请提供原创链接/shuiziliu1025/article/details/50958241
题目： 给出 N 个整数（N可能很大，以致无法装入内存），找出前 K 个最大的整数
【解法一】
如果 N 的数量不是很大，例如在几千个左右，则在这种情况下，那我们就先排序一下，这里快速排序或者推排序都是很好的解决方案，平均时间复杂度为O（N * log2N）。然后取出前 K 个，O（K）。总共时间复杂度O（N * log2N）+ O（K） = O（N * log2N）。
当 K = 1时，上面的算法也是O（N * log2N）的复杂度，而显然我们可以通过 N-1次的比较和交换得到结果。题目要求求出最大的 K 个数，并不需要前 K 个元素有序，后 N-K个元素有序。
如何避免元素的排序，可以使用部分排序的算法，例如选择排序和冒泡排序。把 N 个数中的前 K 大个数排序，复杂度是O（N*K）
这两种复杂度哪一种更好，则取决于 K 的大小， 在 K（K < = log2N）较小的情况下，可以选择部分排序。
【解法二】
回忆一下快速排序，快排中的每一步，都是将待排数据分做两组，其中一组的数据的任何一个数都比另一组中的任何一个大，然后再对两组分别做类似的操作，然后继续下去在本问题中，假设 N 个数存储在数组 S 中，我们从数组 S 中随机找出元素 X，把数组分为两部分 Sa 和 Sb。Sa中的元素大于等于 X， Sb 中的元素小于 X。
这时，存在两种可能性：
1. Sa中元素的个数小于K，Sa中所有的数和Sb中最大的K-|Sa|个元素（|Sa|指Sa中元素的个数就是数组S中最大的K个数。
2. Sa中元素的个数大于或等于K，则需要返回Sa中最大的K个元素。
这样递归下去，不断把问题分解成更小的问题，平均时间复杂度 O（N *log2K）。
【解法三】
寻找 N 个数中最大的 K 个数，本质上就是寻找最大的 K 个数中最小的那个，也就是第 K 大的数。可以使用二分搜索的策略来寻找 N 个数中的第 K 大的数。对于一个给定的数 p，可以在 O（N）的时间复杂度内找出所有不小于 p 的数。假如 N 个数中最大的数为 Vmax，最小的数为 Vmin，那么这 N个数中的第 K 大数一定在区间[Vmin, Vmax]之间。那么，可以在这个区间内二分搜索 N 个数中的第 K大数 p。伪代码如下：
while(Vmax-Vmin > delta)
{
Vmid = Vmin + (Vmax – Vmin) * 0.5;
if(f(arr, N, Vmid) >= K)
Vmin = Vmid;
else
Vmax = Vmid;
}
伪代码中 f（arr, N, Vmid）返回数组arr[0, …, N-1]中大于等于 Vmid 的数的个数。
上述伪代码中，delta 的取值要比所有 N 个数中的任意两个不相等的元素差值之最小值小。如果所有元素都是整数，delta 可以取值 0.5。循环运行之后，得到一个区间（Vmin,Vmax)这个区间仅包含一个元素（或者多个相等的元素）。这个元素就是第 K 大的元素。整个算法的时间复杂度为 O（N *log2（|Vmax – Vmin|/delta））。由于 delta 的取值要比所有 N 个数中的任意两个不相等的元素差值之最小值小，因此时间复杂度跟数据分布相关。在
数据分布平均的情况下，时间复杂度为 O（N * log2（N））。
【解法四】
我们已经得到了三个解法，不过这三个解法有个共同的地方，就是需要对数据访问多次，那么就有下一个问题，如果 N 很大呢，100 亿？（更多的情况下，是面试者问你这个问题）。这个时候数据不能全部装入内存（不过也很难说，谁知道以后会不会 1T 内存比 1 斤白菜还便宜），所以要求尽可能少的遍历所有数据。不妨设 N > K，前 K 个数中的最大 K 个数是一个退化的情况，所有 K 个数就是最大的 K 个数。如果考虑第 K+1 个数 X 呢？如果X比最大的 K 个数中的最小的数 Y 小，那么最大的 K 个数还是保持不变。如果 X 比 Y 大，那么最大的 K个数应该去掉 Y，而包含 X。如果用一个数组来存储最大的 K 个数，每新加入一个数 X，就扫描一遍数组，得到数组中最小的数 Y。用 X 替代 Y，或者保持原数组不变。这样的方法，所耗费的时间为 O（N * K）。进一步，可以用容量为 K 的最小堆来存储最大的 K 个数。最小堆的堆顶元素就是最大 K 个数中最小的一个。每次新考虑一个数 X，如果 X 比堆顶的元素Y 小，则不需要改变原来的堆，因为这个元素比最大的 K 个数小。如果 X 比堆顶元素大，那么用 X 替换堆顶的元素 Y。在 X 替换堆顶元素 Y 之后，X 可能破坏最小堆的结构（每个结点都比它的父亲结点大），需要更新堆来维持堆的性质。更新过程花费的时间复杂度O（log2K）。
因此，算法只需要扫描所有的数据一次，时间复杂度为 O（N * log2K）。在空间方面，由于这个算法只扫描所有的数据一次，因此我们只需要存储一个容量为 K 的堆。大多数情况下，堆可以全部载入内存。如果 K 仍然很大，我们可以尝试先找最大的 K’个元素，然后找第 K’+1个到第 2 * K’个元素，如此类推（其中容量 K’的堆可以完全载入内存）。不过这样，我们需要扫描所有数据 ceil（K/K’）次。
