优先队列的使用 频率前K个
优先队列的使用 频率前K个
力扣题目链接:https://leetcode-cn.com/problems/top-k-frequent-elements/
创建优先队列：
//其实本质上来说，优先队列就是一个大根堆或者是个小根堆
PriorityQueue pq = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer a, Integer b) {
return mp.get(a) - mp.get(b);//这样返回就是小顶堆
//return mp.get(b) - mp.get(a);//这样返回就是大顶堆
}
});//建立一个优先队列,里面存的是每个数
解题思路：
1.先将数组里的数和该数出现的频率存到HashMap里
Map mp=new HashMap<>();
for(int x:nums){
mp.put(x,mp.getOrDefault(x,0)+1);
}//把nums里面的数字和出现的频率存到mp里面去
2.遍历map，用最小堆保存频率最大的k个元素
PriorityQueue pq = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer a, Integer b) {
return mp.get(a) - mp.get(b);//这样返回就是小顶堆
//return mp.get(b) - mp.get(a);//这样返回就是大顶堆
}
});//建立一个优先队列,里面存的是每个数
3.维护这个pq优先队列
for(int x:mp.keySet()){
if(pq.size()4.最后逆序输入到输出数组res中即可
int[] res=new int[k];
for(int i=k-1;i>=0;i--){
res[i]=pq.remove();
}
三：实现代码：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map mp=new HashMap<>();
for(int x:nums){
mp.put(x,mp.getOrDefault(x,0)+1);
}//把nums里面的数字和出现的频率存到mp里面去
// 遍历map，用最小堆保存频率最大的k个元素
PriorityQueue pq = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer a, Integer b) {
return mp.get(a) - mp.get(b);//这样返回就是小顶堆
//return mp.get(b) - mp.get(a);//这样返回就是大顶堆
}
});//建立一个优先队列,里面存的是每个数
int[] res=new int[k];
for(int x:mp.keySet()){
if(pq.size()=0;i--){
res[i]=pq.remove();
}
return res;
}
}
解题总结
这是一道利用数据结构的题目，可见在解算法题的过程中。
不要忽视代码本身数据结构的强大，单调队列，单调栈和哈希表都是比较常用的数据结构。
附上解题结果，好慢啊，不过这题还行，你学废了嘛？