力扣 | 347. 前 K 个高频元素
2023-12-19 22:24:36
leetcode 347 号算法题:前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [2, 1]
输入: nums = [1], k = 1
输出: [1]
1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Problem_347_TopKFrequentElements {
public int [] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num,0) + 1 );
}
PriorityQueue<Integer> pq
= new PriorityQueue<>(k + 1,(a,b) -> count.get(a) - count.get(b));
for (int num : count.keySet()) {
pq.add(num);
if(pq.size() > k) pq.remove();
}
int [] res = new int[k];
int index = 0;
while (!pq.isEmpty()){
res[index++] = pq.remove();
}
return res;
}
}
文章来源:https://blog.csdn.net/qq_37247026/article/details/135092259
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!