347_前 K 个高频元素[MEDIUM]
约 387 字大约 1 分钟
2026-03-10
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
示例 1:
输入:nums = [1,1,1,2,2,3], k = 2
输出:[1,2]示例 2:
输入:nums = [1], k = 1
输出:[1]解题思路
- 先遍历数组,用 hashMap 存频率(key:整数, value:出现次数)
- 用优先队列(最小堆),排序规则:按出现频率
map.get()的值排序 - 将 HashMap 的所有 key 都存入最小堆,只保留前 k 个
- 将堆数组化,返回数组
Java 实现
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 1. 存频率(key:整数, value:出现次数)
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
// 2. 创建小顶堆,堆里存放的是数组元素
// 比较器 (a, b) -> frequencyMap.get(a) - frequencyMap.get(b) 保证频率小的在堆顶
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> frequencyMap.get(a) - frequencyMap.get(b)
);
// 3. 遍历哈希表,维护大小为 k 的小顶堆
for (int key : frequencyMap.keySet()) {
pq.add(key);
// 如果堆的大小超过了 k,就弹出堆顶元素(即当前堆里频率最低的元素)
// 这样保证堆里始终保留的是目前为止频率最高的前 k 个元素
if (pq.size() > k) {
pq.poll();
}
}
// 4. 取出堆中剩下的 k 个元素放入结果数组
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pq.poll();
}
return result;
}
}