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

发布时间:2024年01月23日

目录

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博客icon-default.png?t=N7T8https://blog.csdn.net/zzzzzhxxx/article/details/134104222?spm=1001.2014.3001.5501【LeetCode力扣】189 53 轮转数组 | 最大子数组和-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/zzzzzhxxx/article/details/134095703?spm=1001.2014.3001.5501【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表_力扣234-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/zzzzzhxxx/article/details/133958602?spm=1001.2014.3001.5501

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

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

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

文章来源:https://blog.csdn.net/zzzzzhxxx/article/details/135737266
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。