题目(最小的k个数—牛客网)

输入 n 个整数，找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字，则最小的 4 个数字是 1,2,3,4,。

算法思路一

题目为最小的 k 个数，它是未知数，所以首先应该分类讨论 k 的各种特殊值。
如果 k<=0,或者大于数组大小，则无意义。另外，当 k 刚好就是数组长度时，输入数组即为所求。
对于输入数组的大小也该判断。

我们从求数组任意第 k 个大的数字的问题中得到启发，此问题的相似版本在上一篇文章，采用快速排序的基础思想partition 函数。它既是快速排序的基础，同时也可以用来查找 n 个数中第 k 大的数字。
我们利用快速排序中的分割算法找到那个在 k 位置上的划分点即可，因为划分算法会使得数组中的左半部分数小于划分位置上的数，后半部分的数大于划分位置上的数，那么此时我们的所求就是这左半部分数。(ps:此法会修改原数组，如不需要原数组可使用下述思路，他们适合于处理海量数据的，不需要一次性处理。)

算法思路二

我们利用最大堆来存储这个 k 个数。首先初始将数组前 k 个数送入堆中。然后将其余的数字都和堆顶元素(最大元素)比较,只要比堆顶元素小，我们就删除堆顶元素，将新的元素加入堆中，继续维护堆。最后，堆刚好就维护了最小的 k 个数。

另外为什么不用最小堆呢？因为如果用最小堆，那么我们需要将所有元素送入堆中，那么需要对 n 个元素调堆，而对每个元素的调整时间增加到了O(logn)，最后的总时间复杂度为 O(nlogn)。而使用最大堆进行求解，只需要要 O(nlogk)，关键就在于用于建堆的元素总数。

算法思路三

利用优先队列，其实思想和二类似，但是它比二代码上更简洁。优先队列默认优先值大的排在前面，其实是最大堆实现出来的。

算法实现一

算法实现二

算法实现三

时间复杂度

算法实现一，时间复杂度为O(n)，其余时间复杂度均为O(nlogk)。

参考

[1] <<剑指offer2>>
[2] 牛客网