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

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