力扣 - 347. 前 K 个高频元素
2024-09-08 07:06:39
题目
思路1（哈希表与排序）
- 先用哈希表记录所有的值出现的次数
- 然后将按照出现的次数进行从高到低排序
- 最后取前 k 个就是答案了
代码
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> hashtable = new HashMap<>();
// 统计每个次数出现的次数
for (int num : nums) {
hashtable.put(num, hashtable.getOrDefault(num, 0) + 1);
}
// 排序
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(hashtable.entrySet());
list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o2.getValue().compareTo(o1.getValue());
}
});
// 获取前k高的结果
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = list.get(i).getKey();
}
return res;
}
}
复杂度分析
- 时间复杂度：\(O(NlogN)\)，其中 N 为数组长度，遍历一遍花的时间是N，但是由于排序的时间复杂度是NlogN，所以总的时间复杂度为NlogN
- 空间复杂度：\(O(N)\)，其中 N 为数组长度
思路2（建堆）
- 也是先用哈希表统计出现的次数
- 然后利用小顶堆获取前k高的元素，堆操作的时间复杂度为logk，所以总的就是Nlogk
代码
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 用哈希表存储出现次数
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int num : nums) {
hashtable.put(num, hashtable.getOrDefault(num, 0) + 1);
}
// 使用优先队列
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
// 小顶堆，容量只为k，存储前n大的元素
for (Map.Entry<Integer, Integer> entry : hashtable.entrySet()) {
int element = entry.getKey();
int count = entry.getValue();
if (queue.size() == k) {
// 保证队列存储的前k个元素出现频率都是最多的
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{element, count});
}
} else {
queue.offer(new int[]{element, count});
}
}
// 将优先队列元素出队转换为结果
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = queue.poll()[0];
}
return res;
}
}
复杂度分析
- 时间复杂度：\(O(Nlogk)\)，其中 N 为数组长度，由于堆的大小至多为 k，因此每次堆操作需要 O(logk) 的时间，共需 O(Nlogk) 的时间
- 空间复杂度：\(O(N)\)，其中 N 为数组长度
最新文章
- The method setPositiveButton(int, DialogInterface.OnClickListener) in the type AlertDialog.Builder is not applicable for the arguments
- Vue2.0 + Element-UI + WebAPI实践：简易个人记账系统
- [PHP] 使用Socket提供Http服务
- XCode6的iOS Simulator 文件保存位置
- Codeforces Beta Round #1
- node.js的npm详解
- RPi 2B Documentation
- Educational Codeforces Round 5 B
- Android启动时间测试方法
- 配置Windows Server 2008 允许多用户远程桌面连接
- 查看linux版本和内核信息
- subline text 3的模版设置
- Lintcode解题报告
- VS2013装扩展RazorGenerator
- Linux tar包安装Nginx-1.7.6 (yum方式安装依赖)
- *Boosting*笔记
- 3.5 find() 判断是否存在某元素
- unittest测试用例的执行顺序
- AlwaysOn配置时在连接步骤时报错（35250）
- vi编辑器使用记录