寻找第K大的数

昨天参加阿里巴巴的笔试，有一道题目要求从N个面试的人中挑选出M个成绩最好的人（M<=N, 并假定M个人的成绩都不一样），求挑选程序的最优时间复杂度（）。

选项包括：O(NlogN), O(N*min(M, logN)), O(N*logM), O(N)。

 

O(NlogN）的算法是完全有可能的，使用堆排序，快速排序等将N个元素排序，选取前M个元素即可。

 

O(N*logM）的算法也是有可能的，将前面M个元素构建为最小堆，将后面N-M个元素一次与堆顶比较，如果比堆顶元素大，则与堆顶交换，并将前面M个元素调整为最小堆。

 

在考试时，我觉得不存在O(N)的算法，另外我认为使用最大堆，效率可能更优，即构建最大堆M次，依次挑选M个最大的元素，时间复杂度为O(M*logN)。昨天晚上回去跟同学讨论，他选的O(N)，但也不知道算法如何实现，只是记得寻找从数组中寻找第K大的元素存在O(N)的算法。

 

早上google了一下寻找第K大元素的方法，主要有（假设数组有N个元素）：

1.  使用选择或冒泡算法，排出前K个元素，时间复杂度为O(M*N)。

2.  使用排序算法，将N个元素排序，取第K个，时间复杂度为O(N*logN）。

3.  使用快速排序，从数组中随机找出一个元素X，把数组分成比X小和比X大的两部分，假设比X小的部分元素个数为B，则：

（1）   如果B >= K，则递归从比X小的部分找第K大的元素。

（2）   如果B < K，则递归从比X大的部分找第(K-B)大的元素。

 该算法的时间复杂度接近O(N)（求证明），而且这种方法也能解决上面的笔试题。

4.  使用最小堆，类似笔试题中O(NlogM)的算法。

5.  使用最大堆，类似于笔试题中O(MlogN)的算法。

6.  使用hash表，从大到小统计K个元素即可，时间复杂度为0(N),但提高了空间复杂度。