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

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

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 个数。


目录
相关文章
|
4天前
|
SQL 算法 大数据
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
深入解析力扣181题:超过经理收入的员工(自连接方法详解及模拟面试问答)
|
4天前
|
存储 算法 搜索推荐
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
深入解析力扣179题:最大数(自定义排序法详解及模拟面试问答)
|
4天前
|
SQL 大数据 数据挖掘
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
深入解析力扣178题:分数排名(DENSE_RANK详解及模拟面试问答)
|
4天前
|
SQL 算法 大数据
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
深入解析力扣176题:第二高的薪水(子查询与LIMIT详解及模拟面试问答)
|
4天前
|
存储 算法 数据挖掘
力扣174题动态规划:地下城游戏(含模拟面试)
力扣174题动态规划:地下城游戏(含模拟面试)
|
4天前
|
存储 算法 数据挖掘
力扣173题:二叉搜索树迭代器(含模拟面试)
力扣173题:二叉搜索树迭代器(含模拟面试)
|
4天前
|
SQL 算法 大数据
深入解析力扣177题:第N高的薪水(SQL子查询与LIMIT详解及模拟面试问答)
深入解析力扣177题:第N高的薪水(SQL子查询与LIMIT详解及模拟面试问答)
|
4天前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
4天前
|
算法 数据挖掘 大数据
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
深入解析力扣171题:Excel表列序号(进制转换法详解及模拟面试问答)
|
4天前
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)