戳上面的蓝字“开点工作室”关注我们哦

在程序员面试中，经常会遇到这样一道题目：100000（或很大的一个数）个数找出最小或最大的10个？

【解答要点】 这个问题可以一般化地描述为：在N个数中找最小（或最大）的k个数（k<

最简单的方法是先对N个数排序，再到排好序的数字中找到k个数。显然，整个过程的时间复杂度取决于采用的排序算法。如果是快速排序，时间复杂度为O(Nlog2N)。

更进一步的思路是采用选择性的排序算法，这样效果会更好些。当k≤4时，可以用直接选择排序，比较次数不超过kN。当k>4时，用堆排序更合适，比较次数不超过4N+klog2N（建初始堆所用的比较次数不超过4N，选出k个数的比较次数为klog2N）。所以，采用选择性的排序算法可以得到线性时间复杂度的效果。

另一种线性时间复杂度的方法是：采用上题的方法在n个数中找到第k个数，这时，这个数和以它为枢轴所划分出的左边k-1个数就是最小的k个数。总的比较次数也是线性的。

有没有比较次数接近于N的办法呢？有！具体思路是：先选出n的前k个数，或者把它们初始化为一个大根堆，或者把它们按直接插入排序的方式排好序形成一个长度为k的递增数组。然后从第k+1个元素开始，逐个地处理，或者将它们插入到堆中（当小于堆顶元素时），或者插入到数组中（当小于数组的最后元素时）。二者最坏情况下的时间复杂度分别是O(Nlog2k)和O(kN)。但是在一般情况下，随着n-k个元素被逐个检查，大根堆（或有序数组）中的元素越来越小，使得绝大多数元素只需与堆顶元素（或数组最后一个元素）比较一次。因此，整个过程的比较次数接近于N。实验表明，在N=100000，k=10时，采用大根堆和有序数组两种实现方式，其比较次数相当。由于采用有序数组方式的实现过程更简洁，所以下面给出相应程序。