【LeetCode】347-前K个高频元素
2024-10-06 09:55:22
题目描述
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
解题思路
采用桶排序。所谓桶排序就是设置若干个带下标的桶,每个桶的下标就是桶内元素出现的次数。
想要找到 topk
,只需要从后往前数 k 个元素出来就可以了。
Java 实现
public List<Integer> topKFrequent (int[] nums, int k) {
Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
List<Integer>[] bucket = new List[nums.length + 1];
for (Integer key : frequencyMap.keySet()) {
int freq = frequencyMap.get(key);
if (bucket[freq] == null) {
bucket[freq] = new ArrayList<>();
}
bucket[freq].add(key);
}
List<Integer> ans = new ArrayList<>();
for (int pos = bucket.length - 1; pos >= 0 && ans.size() < k; pos--) {
if (bucket[pos] != null) {
ans.addAll(bucket[pos]);
}
}
return ans;
}
心得体会
使用HashMap
的getOrDefault()
构造每个元素出现频率的集合。
最新文章
- Spring 学习笔记 7. 尚硅谷_佟刚_Spring_Bean 的作用域
- Saas
- Yahoo!网站性能最佳体验的34条黄金守则(转载)
- HDU-4525 威威猫系列故事——吃鸡腿
- OpenStack overview 笔记
- pl/sql developer中的SQL语句
- Codeforces Round #310 (Div. 2) A B C
- zendframework 事件管理(二)
- SpringMVC接收多个对象
- font awesome icon
- Qt_DX
- JDBC基础学习(二)&mdash;PreparedStatement
- 201521145《Java程序设计》第2周学习总结
- Web App、Hybrid App与Native App
- 对于多线程下Servlet以及Session的一些理解
- phalcon框架命名空间
- OpenCV 透视变换实例
- arrays.xml中使用integer-array引用drawable图片资源,代码中如何将这些图片资源赋值到ImageView控件中
- diango admin 添加成员报错
- 多目标遗传算法 ------ NSGA-II (部分源码解析)父、子种群合并 merge.c