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

题目来源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

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