题目描述
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例
提交的代码
你被骗了,我没做出来,能想到的方法时间复杂度是nlogn,还不如不写,想到小顶堆了,但是Java这里我不知道怎么实现:(
学习到的东西
经典使用堆实现,但是个人的Java基础不太好,不会实现堆,是能去找博文看看了,顺便看了下大佬的实现,我是废物。。。
PriorityQueue()这个类是优先级队列也就是堆的实现类,基本方法和队列很像,poll(),peek(),offer(),isEmpty(),size()等。
至于小顶堆查找一个集合中的top k元素,就不多赘述了,大家都会。直接上最后的代码:
import java.util.PriorityQueue;
import java.util.Map;
import java.util.HashMap;
class Solution {
//小顶堆实现前K个高频元素
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
//用PriorityQueue来实现堆
PriorityQueue<int[]> heap=new PriorityQueue<>(k,(element1,element2)->element1[1]-element2[1]);
//生命结果数组
int[] result=new int[k];
int count=0;
//用Map统计每个数字出现的频度
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
//统计前K个高频的元素
Set<Map.Entry<Integer,Integer>> entrySet=map.entrySet();
for(Map.Entry<Integer,Integer> entry:entrySet){
//堆小于k的时候直接放入
if(heap.size()<k){
heap.offer(new int[]{entry.getKey(),entry.getValue()});
}else{
//堆顶出堆,新元素如堆尾部,然后重新调整堆
if(entry.getValue()>heap.peek()[1]){
heap.poll();
heap.offer(new int[]{entry.getKey(),entry.getValue()});
}
}
}
//将堆中的元素都放入结果队列中
while(!heap.isEmpty()){
result[count++]=heap.poll()[0];
}
return result;
}
}
标签:Map,int,元素,LeetCode347,PriorityQueue,heap,new,高频
From: https://www.cnblogs.com/whitePuPigeon/p/17806147.html