【LeetCode】347. Top K Frequent Elements 前 K 个高频元素（Medium）（JAVA）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode】347. Top K Frequent Elements 前 K 个高频元素（Medium）（JAVA），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2033字，纯文字阅读大概需要3分钟。
内容图文
【LeetCode】347. Top K Frequent Elements 前 K 个高频元素（Medium）（JAVA）
题目地址: https://leetcode.com/problems/top-k-frequent-elements/
题目描述：
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
- It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
- You can return the answer in any order.
题目大意
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
解题方法
- 先用 map 把 nums[i] 和对应出现的次数存起来
- 然后就区最大 k 值的问题了，用一个最小堆，来取最大的 k 个值
- 这里用了 java 的 PriorityQueue 优先队列，前 K 个元素直接放进去，K 个之后的元素，如果堆顶元素的个数比当前元素个数小，把堆顶元素取出，把当前元素放进去
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer temp = map.get(nums[i]);
if (temp == null) {
map.put(nums[i], 1);
} else {
map.put(nums[i], 1 + temp);
}
}
PriorityQueue<int[]> queue = new PriorityQueue<>(k, (a, b) -> (a[1] - b[1]));
int count = 0;
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
if (count < k) {
queue.offer(new int[]{entry.getKey(), entry.getValue()});
count++;
} else if (queue.peek()[1] < entry.getValue()) {
queue.poll();
queue.offer(new int[]{entry.getKey(), entry.getValue()});
}
}
int[] res = new int[k];
for (int i = res.length - 1; i >= 0; i--) {
res[i] = queue.poll()[0];
}
return res;
}
}
执行耗时:13 ms,击败了94.69% 的Java用户
内存消耗:40.8 MB,击败了97.34% 的Java用户
内容总结
以上是互联网集市为您收集整理的【LeetCode】347. Top K Frequent Elements 前 K 个高频元素（Medium）（JAVA）全部内容，希望文章能够帮你解决【LeetCode】347. Top K Frequent Elements 前 K 个高频元素（Medium）（JAVA）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。