目录
1、题目介绍
2、解题思路
2.1、优先队列解法
2.2、top-k问题解法
1、题目介绍
原题链接：面试题 17.14. 最小K个数 - 力扣（LeetCode）
题目要求非常简短，也非常简单，就是求一组数中的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 个数。
更多【LeetCode刷题】推荐：
【LeetCode力扣】42. 接雨水-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/134104222?spm=1001.2014.3001.5501【LeetCode力扣】189 53 轮转数组 | 最大子数组和-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/134095703?spm=1001.2014.3001.5501【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表_力扣234-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133958602?spm=1001.2014.3001.5501
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！文章来源地址https://www.toymoban.com/news/detail-822632.html
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！文章来源：https://www.toymoban.com/news/detail-822632.html
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
到了这里，关于【LeetCode力扣】面试题 17.14. 最小K个数（top-k问题）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
