题目

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

解析

思路一

显然最简答做法就是对原数组排序，取前k个就行。

Note: 这里可以分情况的：

1. 如果k远小于n, 可以利用一次冒泡或者选择算法，选择出当前序列中最小的值，复杂度为O(nk)

2. 如果k没有远小于n, 那么选择O(nlogn)算法最佳

    /**      * 排序的做法      * @param input      * @param k      * @return      */     public static ArrayList GetLeastNumbers_Solution(int [] input, int k) {         ArrayList result = new ArrayList();         if(input == null || k  input.length) {             return result;         }         Arrays.sort(input);         for(int i = 0; i 
思路二
我们注意到题目并没有要求输出的最小k个数必须是有序的，所以我们可以利用快排中partion函数的思想来做做题。 因为partion可以使得序列分为2部分：左边的值都小于哨兵，右边的值都大于哨兵。所以我们只要找到处于第k位置的哨兵即可，也就是说找到第k大的值所在的位置即可，那么它的左边的k-1值都小于等于第k大值。显然，前k个值即为我们所求的最小k个数。在我们的划分过程有3种情况：

哨兵的位置大于k，说明第k大的数在左边，继续递归处理左部分即可。
哨兵的位置小于k，说明第K大的数在右边，继续递归处理有部分即可。
哨兵的位置等于k，说明该哨兵即为第K大的值，其左边k-1个数都小于等于它，因此输出前k个即为所求的结果。

    /**      * 基于快排的划分函数的思想来做的。      * @param input      * @param k      * @return      */     public static ArrayList GetLeastNumbers_Solution2(int [] input, int k) {         ArrayList result = new ArrayList();         if(input == null || k  input.length) {             return result;         }         findKthValue(input, 0, input.length - 1, k - 1);         for(int i = 0; i  k) {                 findKthValue(input, low, index - 1, k);             }else if(index 
思路3
这是典型的Top-K问题，即从n个数中找出最小的k个数或者最大的k个数问题。
我们通常的做法用一个容量为k的容器来存放这k个最小的值。我们只需遍历一遍原数组，就能得到最小的k个数。

起初容器是空，当已遍历的数的个数小于容器的容量k时，直接向容器中添加该值。
当容器的容量已满，则判断该容器中最大值是否大于待插入的点：

若大于，则从容器中删除该最大值，添加待插入的点
若小于或者等于，则不做任何操作，继续遍历下一个值


问题转化为如何高效率得到容器中的最大值。一个优雅的数据结构完美的解决此题，即堆结构，分为大根堆或者小根堆。显然这里应该选择大根堆。在大根堆中，根节点大于左子树和右子树中所有点，所以我们只需访问根节点即可得到k容量的最大值，且数据结构可以对插入的值进行动态调整堆结构，使得满足大根堆。关于堆的具体代码，以后我单独写一个博客，这里不再累述了。
在Java中，没有专门的堆数据结果，不过有基于堆结构的优先队列，所以这里采用优先队列并自定义比较器，来满足大根堆的需求。
     /**      * Topk问题      * @param input      * @param k      * @return      */     public static ArrayList GetLeastNumbers_Solution3(int [] input, int k) {         ArrayList result = new ArrayList();         if(input == null || k  input.length) {             return result;         }         PriorityQueue priorityQueue = new PriorityQueue(k, new Comparator() {             //因为要满足大根堆需求，所以使用自定义比较器，比较策略为o1大于o2时，o1放o2的前面             @Override             public int compare(Integer o1, Integer o2) {                 return o2 - o1;             }         });         for(int i = 0; i 
总结
多结合排序算法和常见的数据结构来简化题目。
SpecialYang---原文地址：https://juejin.im/post/5b567b49f265da0f8d3662eb