题目描述:
给你一个整数数组 nums
和一个整数 k
,请你返回其中出现频率前 k
高的元素。你可以按 任意顺序 返回答案。
样例:
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示:
1 <= nums.length <= 10^5
k
的取值范围是 [1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一,换句话说,数组中前
k
个高频元素的集合是唯一的
Java程序:
class Solution {
public int[] topKFrequent(int[] nums, int k) {//小顶堆
Map<Integer,Integer> map=new HashMap<>();
for (int i = 0; i <nums.length ; i++) {
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
PriorityQueue<int[]> priorityQueue=new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if (priorityQueue.size() < k) {
priorityQueue.add(new int[]{entry.getKey(),entry.getValue()});
}else{
if (entry.getValue() > priorityQueue.peek()[1]) {
priorityQueue.poll();
priorityQueue.add(new int[]{entry.getKey(),entry.getValue()});
}
}
}
int[] ans=new int[k];
for(int i=k-1;i>=0;i--){
ans[i]=priorityQueue.poll()[0];
}
return ans;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)