1、题目介绍
题目要求非常简短，也非常简单，就是求一组数中的k个最小数。
2、解题思路
如果在正常刷题过程中遇到这种题，那么这道题毋庸置疑是秒杀题，使用最简单的冒泡排序亦或者是直接使用Java中Arrays类的方法sort直接排序后，再取出前k个值。
但是，这是一道面试题，面试题的精髓就是要尽可能的压缩时间复杂度和空间复杂度，以达到给面试官眼前一亮的效果。显然直接使用自带的排序很难给面试官眼前一亮的效果，而该题有一种统称叫：top-k问题，使用top-k问题经典的解法可以将时间复杂度控制在O(N*logK)，空间复杂度O(K)。
下面将使用两种方法来解题，一种是正常解法，一种是top-k问题解法。
2.1、优先队列解法
直接使用优先队列将数组arr中的所有元素入队，最终队中的队头便是最小值，只需要依次出队并存入到返回数组ret中即可。
【完整代码】
class Solution { public int[] smallestK(int[] arr, int k) { int[] ret = new int[k]; if(k == 0) { return ret; } Queue<Integer> queue = new PriorityQueue<>(); //优先队列，默认小根堆 for(int i = 0 ; i < arr.length; i++) { //依次入队 queue.offer(arr[i]); } for(int i = 0; i < k; i++) { //依次出队并存入 ret[i] = queue.poll(); } return ret; } }
但是显然这样的解法非常的普遍，并不能让面试官眼前一亮，下面带大家认识一下另一个解法，也就是top-k问题的解法。
2.2、top-k问题解法
top-k问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于top-k问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
【思路讲解】
以题目示例为例：
首先用前k个元素建大根堆
用剩余的N-K个元素依次与堆顶元素来比较，如果此时小于堆顶（即队头）则替换堆顶元素。
这样做的原理非常简单：因为此时是大根堆，队头元素即为堆中最大值，如果此时堆外元素还有比堆顶元素小的，那么证明堆顶元素肯定不属于k个最小元素中的一个，此时需要将堆顶（即队头）出队，然后将该元素入队，并重新调整成大根堆。
此时从上图可发现，2小于堆顶（即队头）7，因此需要将7出队，2入队，并调整堆。
此时从上图可发现，4小于堆顶（即队头）5，因此需要将5出队，4入队，并调整堆。
而后面的6，8都不小于堆顶4，因此堆没有变化，最后得到的大根堆内的所有元素即题目所求的元素，只需要将堆内元素依次出队即可。
【完整代码】
class Solution { public int[] smallestK(int[] arr, int k) { int[] ret = new int[k]; if(k == 0) { return ret; } Queue<Integer> queue = new PriorityQueue<>(new ComparaBig()); for(int i = 0; i < k; i++) { //用前k个元素建大根堆 queue.offer(arr[i]); } for(int i = k; i < arr.length; i++) { //堆顶元素与后续的n-k个元素依次比较 if(queue.peek() > arr[i]) { //当发现当前元素小于堆顶元素时，出队堆顶元素，入队当前元素 queue.poll(); queue.offer(arr[i]); } } for(int i = 0; i < k; i++) { //将堆中所有元素出队，依次放到返回数组ret中 ret[i] = queue.poll(); } return ret; } } //Java自带的优先队列为小根堆，该题需要使用大根堆，因此需要重写比较器 class ComparaBig implements Comparator<Integer> { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }
时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
空间复杂度：O(k)，因为大根堆里最多 k 个数。
