【347 前K个高频元素】
前言题目源码
前言
国庆给自己放了三天假,开始干活,今天的题目是topK问题,印象中是个挺经典的堆的题解,维护一个出现频率数组
题目
官方题目
源码
class Solution {
public int[] topKFrequent(int[] nums
, int k
) {
Map
<Integer,Integer> occure
= new HashMap<Integer,Integer>();
for (int num
:nums
){
occure
.put(num
,occure
.getOrDefault(num
,0)+1);
}
PriorityQueue
<int []>queue
=new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[]m
,int[]n
){
return m
[1]-n
[1];
}
});
for(Map
.Entry
<Integer, Integer> entry
: occure
.entrySet()){
int num
=entry
.getKey();
int count
=entry
.getValue();
if(queue
.size()==k
){
if(queue
.peek()[1]<count
){
queue
.poll();
queue
.offer(new int[]{num
,count
});
}
}else{
queue
.offer(new int[]{num
,count
});
}
}
int []res
=new int[k
];
for (int i
=0;i
<k
;i
++){
res
[i
]=queue
.poll()[0];
}
return res
;
}
}
哈哈哈哈,看到一个python逆天解不得不说python函数库真的丰富,仅供娱乐。
class Solution:
def topKFrequent(self
, nums
: List
[int], k
: int) -> List
[int]:
return [num
for num
, _
in Counter
(nums
).most_common
(k
)]