用PriorityQueue解决选择最小的K个数问题

青旅半醒 2022-03-06 11:52 147阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70]  
Java没有堆的实现，现场写也来不及，有的文献说用TreeSet，比如剑指offer，但是TreeSet是一个set，相同的数只能存一个，个人感觉不合适，相比之下，Java中的PriorityQueue倒是一个不错的选择。用PriorityQueue的实现的代码如下：

/**
    	 * 用PriorityQueue实现选择最小的k个数
    	 * @param array	数组
    	 * @param k
    	 * @return
    	 */
    	public int[] selectKmin(int[] array,int k){
    		int[] res = new int[k];	
    		//创建一个降序排列的PriorityQueue，自定义比较器作为参数
    		PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(k,new Comparator<Integer>(){
     
    			@Override
    			public int compare(Integer o1, Integer o2) {
    				return o2-o1;
    			}});
    		
    		for(int i=0;i<array.length;i++){
    			if(priorityQueue.size()<k){
    				priorityQueue.add(array[i]);
    			}else{
    				int maxInQueue = priorityQueue.peek();
    				if(maxInQueue>array[i]){//每次取数与堆顶的元素进行比较，
    				//如果堆顶元素大，则删除堆顶元素，并添加这个新数到堆中
    					priorityQueue.poll();
    					priorityQueue.add(array[i]);
    				}
    			}
    		}
    		
    		//升序存放
    		for(int i=0;i<k;i++){
    			res[k-i-1] = priorityQueue.poll();
    		}
    		
    		return res;
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70]: /images/20220303/16df79b7f1274c34a410c633e67ead4b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关算法：最小的k个数

![d42d543de3045d3132ea41a5defad606.jpeg][] 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、

以你之姓@/ 2024年04月03日 14:17/ 0 赞/ 86 阅读

相关最小K个数

[14天阅读挑战赛][14] 目录最小K个数方法一方法二 -------------------- 最小K个数设计一个算法，找出数组中最小的k个数

阳光穿透心脏的1/2处/ 2023年10月10日 15:13/ 0 赞/ 90 阅读

相关求最小的k个数

文章目录求最小的k个数 1.题目描述 2.题目链接 3.解题方法求最小的k个数 1.题目描述 ![在这里插

怼烎@/ 2022年08月30日 04:29/ 0 赞/ 201 阅读

相关最小的k个数

题目描述：查找最小的K个数题目：输入n个整数，输出其中最小的K个数例如，输入1、2、3、4、5、6、7、8这8个数字，则最小的4个数字为1、2、3、4。解题思路

左手的ㄟ右手/ 2022年08月20日 11:27/ 0 赞/ 189 阅读

相关 java_最小的k个数

package com.zhiru; / 求一个序列中最小的k个数 / public class TopK {

左手的ㄟ右手/ 2022年08月12日 00:20/ 0 赞/ 212 阅读

相关寻找最小的k个数

寻找最小的k个数 1. 题目描述在一个长度为n的数组中，寻找最小的k个数。（最大的k个数解法类似） 2. 排序法想法比较简

绝地灬酷狼/ 2022年08月05日 17:59/ 0 赞/ 188 阅读

相关问题 : 最小的K个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。输入每个测试案例包括2行：

以你之姓@/ 2022年06月10日 06:24/ 0 赞/ 220 阅读

相关最小的K个数

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4

谁借莪１个温暖的怀抱￠/ 2022年03月20日 03:24/ 0 赞/ 229 阅读

相关最小的K个数

时间限制：1秒空间限制：32768K 热度指数：363913 本题知识点：数组算法知识视频讲解题目描述输入n个整数，找出其中最小的K个数。例如输入4,

比眉伴天荒/ 2022年03月09日 10:46/ 0 赞/ 231 阅读

相关用PriorityQueue解决选择最小的K个数问题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

青旅半醒/ 2022年03月06日 11:52/ 0 赞/ 148 阅读