【LeetCode力扣】面试题 17.14. 最小K个数（top-k问题）

怼烎@ 2024-04-20 11:40 77阅读 0赞

**目录**

1、题目介绍

2、解题思路

2.1、优先队列解法

2.2、top-k问题解法

![2d25b46a2e254c8f89778ce7363f0c4b.gif][]

## 1、题目介绍 ##

**原题链接：**[面试题 17.14. 最小K个数 - 力扣（LeetCode）][17.14. _K_ - _LeetCode]

![2c139bda05c34aa6ad8dd5d969a28f4b.png][]

> 题目要求非常简短，也非常简单，就是求一组数中的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个最小或者最大的元素。

**【思路讲解】**

> **以题目示例为例：**
> 
> ![5886666344f94f1e9d88d147be3fb324.png][]
> 
> 首先用前k个元素建大根堆

![f7788222c89146a7988e1dc22765eac7.png][]

> 用剩余的N-K个元素依次与堆顶元素来比较，如果此时小于堆顶（即队头）则替换堆顶元素。
> 
> 这样做的原理非常简单：**因为此时是大根堆，队头元素即为堆中最大值，如果此时堆外元素还有比堆顶元素小的，那么证明堆顶元素肯定不属于k个最小元素中的一个，此时需要将堆顶（即队头）出队，然后将该元素入队，并重新调整成大根堆。**

![ca8998913b4c4ec98fec2ec012c55647.png][]

> 此时从**上图**可发现，2小于堆顶（即队头）7，因此需要将7出队，2入队，并调整堆。

![1bcc26539ea94ba38fd7301fc51b976f.png][]

> 此时从**上图**可发现，4小于堆顶（即队头）5，因此需要将5出队，4入队，并调整堆。

![c153db114e564a3cb5db095942992567.png][]

> 而后面的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 个数。

![10487918443944209b735225981b76d7.gif][]

**更多【LeetCode刷题】推荐：**

[【LeetCode力扣】42. 接雨水-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/134104222?spm=1001.2014.3001.5501][LeetCode_42. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_134104222_spm_1001.2014.3001.5501][【LeetCode力扣】189 53 轮转数组 | 最大子数组和-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/134095703?spm=1001.2014.3001.5501][LeetCode_189 53 _ _ _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_134095703_spm_1001.2014.3001.5501][【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表\_力扣234-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/133958602?spm=1001.2014.3001.5501][LeetCode_234 _ _ _ _ _234-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133958602_spm_1001.2014.3001.5501]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[2d25b46a2e254c8f89778ce7363f0c4b.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/fcf9a9ed3a064fe1bc8679bb5afb5733.gif
[17.14. _K_ - _LeetCode]: https://leetcode.cn/problems/smallest-k-lcci/description/
[2c139bda05c34aa6ad8dd5d969a28f4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/7fa9f17137464ccfa9b8dcdca4f43a76.png
[5886666344f94f1e9d88d147be3fb324.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b007a79d23984041986ab08b2087b33b.png
[f7788222c89146a7988e1dc22765eac7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/fd1f4d9bb8fd45dd89fb8d92f5ac33ec.png
[ca8998913b4c4ec98fec2ec012c55647.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/85aedb3d30e94d50887c62a829c53498.png
[1bcc26539ea94ba38fd7301fc51b976f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/71de451774934f76b2146cc0625e85cf.png
[c153db114e564a3cb5db095942992567.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/9b4d74a0360045faa309dada3a8de3b0.png
[10487918443944209b735225981b76d7.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/b91b920490eb4a8c878a2f0d087200a3.gif
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[LeetCode_42. _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_134104222_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/134104222?spm=1001.2014.3001.5501
[LeetCode_189 53 _ _ _-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_134095703_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/134095703?spm=1001.2014.3001.5501
[LeetCode_234 _ _ _ _ _234-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133958602_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/133958602?spm=1001.2014.3001.5501