前 K 个高频元素
# 📃 题目描述
题目链接:
- 347. 前 K 个高频元素 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 剑指 Offer II 060. 出现频率最高的 k 个数字 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
# 🔔 解题思路
经典 TopK 问题
在面试过程中遇到这个题目,首先要想到的是解决这个题目需要用到哈希表。这个题目的输入是一个数组,哈希表可以用来统计数组中数字出现的频率,哈希表的键是数组中出现的数字,而值是数字出现的频率
接下来找出出现频率最高的 k 个数字,可以使用小根堆,每次弹出堆顶元素(出现频率最低的元素),直到堆中留下的元素个数为 k 个,就是出现频率前 k 高的元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if (nums == null || nums.length < k) {
return new int[0];
}
// 存储最终结果
int[] res = new int[k];
// 计算每个元素出现的次数
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 按照出现频率构造小顶堆
PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
(o1, o2) -> o1.getValue() - o2.getValue()
);
// 等价于
// PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
// new Comparator<Map.Entry<Integer, Integer>>() {
// @Override
// public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
// return o1.getValue() - o2.getValue();
// }
// }
// );
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (minHeap.size() < k) {
minHeap.offer(entry);
}
else {
if (entry.getValue() > minHeap.peek().getValue()) {
minHeap.poll();
minHeap.offer(entry);
}
}
}
for (int i = 0; i < k; i ++) {
res[i] = minHeap.poll().getKey();
}
return res;
}
}
只用哈希表也能做这道题,不过相对来说考虑的东西会多一点
# 💥 复杂度分析
- 时间复杂度:O(Nlogk),其中 N 为数组的长度。我们首先遍历原数组,并使用哈希表记录出现次数,每个元素需要 O(1) 的时间,共需 O(N) 的时间。随后,我们遍历哈希表构造小顶堆,由于堆的大小至多为 k,因此每次堆操作需要 O(logk) 的时间,共需 O(Nlogk) 的时间。二者之和为 O(Nlogk)
- 空间复杂度:O(N)。哈希表的大小为 O(N),而堆的大小为 O(k),共计为 O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10