更换网站后台,wordpress qqkf,百度度小店申请入口,扬州市住房和城乡建设网站目录
1、题目介绍
2、解题思路
2.1、优先队列解法
2.2、top-k问题解法 1、题目介绍
原题链接#xff1a;面试题 17.14. 最小K个数 - 力扣#xff08;LeetCode#xff09; 题目要求非常简短#xff0c;也非常简单#xff0c;就是求一组数中的k个最小数。 2、解题思路 …目录
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;}QueueInteger 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入队并调整堆。 而后面的68都不小于堆顶4因此堆没有变化最后得到的大根堆内的所有元素即题目所求的元素只需要将堆内元素依次出队即可。 【完整代码】
class Solution {public int[] smallestK(int[] arr, int k) {int[] ret new int[k];if(k 0) {return ret;}QueueInteger 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 ComparatorInteger { Overridepublic 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?spm1001.2014.3001.5501【LeetCode力扣】189 53 轮转数组 | 最大子数组和-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/134095703?spm1001.2014.3001.5501【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表_力扣234-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133958602?spm1001.2014.3001.5501 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
