网站建设团队介绍,制作app免费网站模板下载,wordpress 文章主题,智能制造公司描述
给定一个长度为 n 的可能有重复值的数组#xff0c;找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字#xff0c;则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围#xff1a;0≤k,n≤10000#xff0c;数组中每个数的大小0≤val≤1000
要…描述
给定一个长度为 n 的可能有重复值的数组找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围0≤k,n≤10000数组中每个数的大小0≤val≤1000
要求空间复杂度 O(n) 时间复杂度 O(nlogk) 示例1
输入
[4,5,1,6,2,7,3,8],4
返回值
[1,2,3,4]
说明
返回最小的4个数即可返回[1,3,2,4]也可以
示例2
输入
[1],0
返回值
[]示例3
输入
[0,1,2,1,2],3
返回值
[0,1,1]
思路分析
该题可以使用优先队列PriorityQueue来解决这个问题
因为PriorityQueue添加进去的数据会默认自然排序想以升序检索元素。在这种情况下优先队列的头是最小的元素。检索到该元素后下一个最小的元素将成为队列的头。
那么可以把input数组添加进去然后循环取优先队列的头元素添加进去集合re里面。
代码
import java.util.*;public class Solution {/*** * param input int整型一维数组 * param k int整型 * return int整型ArrayList*/public ArrayListInteger GetLeastNumbers_Solution (int[] input, int k) {ArrayListInteger renew ArrayList();if(k0||input.length0) return re;PriorityQueueInteger qnew PriorityQueue();for(int i0;iinput.length;i){q.add(input[i]);}for(int i0;ik;i){re.add(q.poll());}return re;}
}
