天天消息!leetcode[栈与队列—中等]347.前K个高频元素

2022-10-31 08:56:16

来源:阿里云

题目来源leetcode

leetcode地址:347.前K个高频元素,难度:中等。


(资料图片)

题目描述(摘自leetcode):

给你一个整数数组nums和一个整数k,请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。示例1:输入:nums=[1,1,1,2,2,3],k=2输出:[1,2]示例2:输入:nums=[1],k=1输出:[1]提示:1<=nums.length<=105k的取值范围是[1,数组中不相同的元素的个数]题目数据保证答案唯一,换句话说,数组中前k个高频元素的集合是唯一的

本地调试代码:

classSolution{publicint[]topKFrequent(int[]nums,intk){...}publicstaticvoidmain(String[]args){int[]nums=newint[]{1,1,1,2,2,3};System.out.println(Arrays.toString(newSolution.topKFrequent(nums,2)));}}

题解

NO1:哈希表+优先队列

思路:先使用哈希表来进行统计对应值的频率,之后创建一个优先队列设置一个从小到大排序的比较器,每次插入一组key、value后,判断当前的容量是否>k个,若是大于了直接将队头的出队(在队列里频率最小的),最终遍历取出队列中的k组数据即可。

代码:

publicint[]topKFrequent(int[]nums,intk){//使用map来进行统计指定指定数的频率,key为num,value为频率Mapmap=newHashMap<>;for(intnum:nums){map.put(num,map.getOrDefault(num,0)+1);}Set>entries=map.entrySet;//创建优先队列,传入Comparator匿名接口类,插入队列的元素从小到达排列PriorityQueue>queue=newPriorityQueue<>((o1,o2)->o1.getValue-o2.getValue);for(Map.Entryentry:entries){queue.offer(entry);if(queue.size>k){//一旦队列中的数量大于k,直接将频率最小的出队(队头)queue.poll;}}//最终取出对应的最大k值int[]maxNums=newint[k];for(inti=k-1;i>=0;i--){maxNums[i]=queue.poll.getKey;}returnmaxNums;}

NO2:排序遍历+优先队列

思路:首先进行从小到大排序,之后对整个数组进行遍历,以[i]!=[i-1]来作为存储到队列的依据,队列按照从大到小排序,每次入队后判断是否>k个,若是大于出队。最终遍历k个即可获取到前k个高频元素。

代码:

publicint[]topKFrequent(int[]nums,intk){Arrays.sort(nums);//优先队列,按照频率从小到大排列(Comparator返回值为负数就从小到大排列,若是正数从大到小)PriorityQueuequeue=newPriorityQueue((o1,o2)->o1[1]-o2[1]);//对数组进行遍历操作inti=1;intj=1;for(;ik){//一旦大于原本k个数量就进行移除queue.poll;}j=1;}}queue.offer(newint[]{nums[i-1],j});if(queue.size>k){queue.poll;}//从队列中取出k个int[]maxNums=newint[k];for(intl=0;l

关键词: 优先队列 题目数据