题目标题

在未排序的数组中找到第k个最大的元素,如果是海量数据该怎么办?要求时间复杂度(nlogn)。

参考解析

【解法一】先排序,然后输出第k个位置上的数
我们先假设元素的数量不大,例如在几千个左右,在这种情况下,那我们就排序一下吧。在这里,快速排序或堆排序都是不错的选择,他们的平均时间复杂度 都是 O(N logN)。然后取出前 K 个,O(K)。总时间复杂度 O(N logN)+ O(K) = O(N logN)。
你一定注意到了,当 K=1 时,上面的算法也是 O(N
logN)的复杂度,而显然我们可以通过 N-1 次的比较和交换得到结果。上面的算法把整个数组都进行了排序,而原题目只要求最大的 K 个数,并不需要前 K 个数有序,也不需要后 N-K 个数有序。
怎么能够避免做后 N-K 个数的排序呢?我们需要部分排序的算法,选择排序和交换排序都是不错的选择。把 N 个数中的前 K 大个数排序出来,复杂度是O(N K)。那一个更好呢?O(N logN)还是 O(N * K)?这取决于 K 的大小,这是你需要在面试者那里弄清楚的问题。在 K(K < = logN)较小的情况下,可以选择部分排序。
【解法二】改进的快速排序方法:避免对所有的数排序,利用快速排序分堆,然后递归另外一半(不需要两半都递归),直到最终所有小于基准数的个数为K
回忆一下快速排序,快排中的每一步,都是将待排数据分做两组,其中一组的数据的任何一个数都比另一组中的任何一个大,然后再对两组分别做类似的操作,然后继续下去……
在本问题中,假设 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 logK)。
    【解法三】二分搜索法:直接划定中值区间,通过比较的方法,找到第K个数所在的数值区间,然后二分搜索递归下去
    【解法四】堆排序法:非常适合内存有限,数据海量的情况
    我们已经得到了三个解法,不过这三个解法有个共同的地方,就是需要对数据访问多次,那么就有下一个问题,如果 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’的堆可以完全载入内存)。不过这样,我们需要扫描所有数据 ceil1(K/K’)次。