347. 前 K 个高频元素
题目描述
输入一个整数数组 nums 和一个整数 k。统计每个不同的数在数组中出现了几次。
按出现次数从多到少排，返回排在前 k 位的那些数。结果中的元素顺序不限。
题目保证这 k 个数构成的集合是唯一确定的。
示例 1
输入：nums = [1,1,1,2,2,3], k = 2 输出：[2,1]
解释：1 出现 3 次，2 出现 2 次，3 只出现 1 次，取前两个。
示例 2
输入：nums = [1], k = 1 输出：[1]
示例 3
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2 输出：[1,2]
解释：1 和 2 各出现 4 次，3 出现 2 次。
数据范围
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4k在[1, 数组中不同元素的个数]范围内- 答案集合唯一。
进阶：算法的时间复杂度必须低于 O(n log n)，n 为数组长度。
解题思路：哈希计数 + 大小为 k 的小根堆
统计频率后维护最小堆。
为什么正确
堆中保存频率最高的 k 个元素。
复杂度分析
时间 O(n log k)，额外空间 O(n)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
import heapq
from collections import Counter
class Solution:
def topKFrequent(self,a,k):
h=[]
for x,c in Counter(a).items():heapq.heappush(h,(c,x));heapq.heappop(h) if len(h)>k else None
return [x for c,x in h]class Solution {
public int[] topKFrequent(int[] nums, int k) {
PriorityQueue<int[]> h = new PriorityQueue<>((p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
h.offer(new int[]{e.getValue(), e.getKey()});
if (h.size() > k) h.poll();
}
int[] res = new int[h.size()];
for (int i = 0; !h.isEmpty(); i++) res[i] = h.poll()[1];
return res;
}
}class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> h;
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
for (auto& [x, c] : cnt) {
h.push({c, x});
if ((int)h.size() > k) h.pop();
}
vector<int> res;
for (; !h.empty(); h.pop()) res.push_back(h.top().second);
return res;
}
};type pairHeap [][2]int
func (h pairHeap) Len() int { return len(h) }
func (h pairHeap) Less(i, j int) bool {
if h[i][0] != h[j][0] {
return h[i][0] < h[j][0]
}
return h[i][1] < h[j][1]
}
func (h pairHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *pairHeap) Push(v interface{}) { *h = append(*h, v.([2]int)) }
func (h *pairHeap) Pop() interface{} {
old := *h
v := old[len(old)-1]
*h = old[:len(old)-1]
return v
}
func topKFrequent(nums []int, k int) []int {
h := &pairHeap{}
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
for x, c := range cnt {
heap.Push(h, [2]int{c, x})
if h.Len() > k {
heap.Pop(h)
}
}
res := []int{}
for _, p := range *h {
res = append(res, p[1])
}
return res
}const less = (a, b) => a[0] !== b[0] ? a[0] < b[0] : a[1] < b[1];
function heappush(h, v) {
h.push(v);
for (let i = h.length - 1; i > 0; ) {
const p = (i - 1) >> 1;
if (!less(h[i], h[p])) break;
[h[i], h[p]] = [h[p], h[i]];
i = p;
}
}
function heappop(h) {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ; ) {
let s = i;
for (const c of [2 * i + 1, 2 * i + 2]) if (c < h.length && less(h[c], h[s])) s = c;
if (s === i) break;
[h[i], h[s]] = [h[s], h[i]];
i = s;
}
}
return top;
}
var topKFrequent = function(nums, k) {
const h = [];
const cnt = new Map();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
for (const [x, c] of cnt) {
heappush(h, [c, x]);
if (h.length > k) heappop(h);
}
return h.map(([c, x]) => x);
};const less = (a: number[], b: number[]): boolean => a[0] !== b[0] ? a[0] < b[0] : a[1] < b[1];
function heappush(h: number[][], v: number[]): void {
h.push(v);
for (let i = h.length - 1; i > 0; ) {
const p = (i - 1) >> 1;
if (!less(h[i], h[p])) break;
[h[i], h[p]] = [h[p], h[i]];
i = p;
}
}
function heappop(h: number[][]): number[] {
const top = h[0], last = h.pop()!;
if (h.length) {
h[0] = last;
for (let i = 0; ; ) {
let s = i;
for (const c of [2 * i + 1, 2 * i + 2]) if (c < h.length && less(h[c], h[s])) s = c;
if (s === i) break;
[h[i], h[s]] = [h[s], h[i]];
i = s;
}
}
return top;
}
function topKFrequent(nums: number[], k: number): number[] {
const h: number[][] = [];
const cnt = new Map<number, number>();
for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
for (const [x, c] of cnt) {
heappush(h, [c, x]);
if (h.length > k) heappop(h);
}
return h.map(([c, x]) => x);
};其他解法
堆的做法稳定 O(n log k)，可以边读边维护；快速选择平均 O(n)，但需要拿到全部数据后才能划分，最坏情况下是 O(n²)。
解法 2：哈希计数 + 快速选择 时间 平均 O(n)，最坏 O(n²)，空间 O(n)
先用哈希表统计每个数的出现次数，得到 (数字, 次数) 数组。然后像快速排序一样按次数做三路划分：取中间元素的次数为基准，把数组分成大于、等于、小于基准三段。第 k 大的位置落在哪一段，就只在哪一段继续划分。结束后前 k 个元素就是答案。
平均线性，比堆少一个 log k。但会打乱数组顺序，不适合数据流场景，基准选得不好时会退化为 O(n²)。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
items = list(collections.Counter(nums).items())
lo, hi, t = 0, len(items) - 1, k - 1
while lo < hi:
p = items[(lo + hi) // 2][1]
lt, i, gt = lo, lo, hi
while i <= gt:
c = items[i][1]
if c > p:
items[lt], items[i] = items[i], items[lt]
lt += 1
i += 1
elif c < p:
items[gt], items[i] = items[i], items[gt]
gt -= 1
else:
i += 1
if t < lt:
hi = lt - 1
elif t > gt:
lo = gt + 1
else:
break
return [x for x, _ in items[:k]]class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
int[][] items = new int[cnt.size()][];
int idx = 0;
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) items[idx++] = new int[]{e.getKey(), e.getValue()};
int lo = 0, hi = items.length - 1, t = k - 1;
while (lo < hi) {
int p = items[(lo + hi) / 2][1];
int lt = lo, i = lo, gt = hi;
while (i <= gt) {
int c = items[i][1];
if (c > p) swap(items, lt++, i++);
else if (c < p) swap(items, gt--, i);
else i++;
}
if (t < lt) hi = lt - 1;
else if (t > gt) lo = gt + 1;
else break;
}
int[] res = new int[k];
for (int j = 0; j < k; j++) res[j] = items[j][0];
return res;
}
private void swap(int[][] a, int i, int j) {
int[] tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
vector<pair<int, int>> items(cnt.begin(), cnt.end());
int lo = 0, hi = (int)items.size() - 1, t = k - 1;
while (lo < hi) {
int p = items[(lo + hi) / 2].second;
int lt = lo, i = lo, gt = hi;
while (i <= gt) {
int c = items[i].second;
if (c > p) swap(items[lt++], items[i++]);
else if (c < p) swap(items[gt--], items[i]);
else i++;
}
if (t < lt) hi = lt - 1;
else if (t > gt) lo = gt + 1;
else break;
}
vector<int> res;
for (int j = 0; j < k; j++) res.push_back(items[j].first);
return res;
}
};func topKFrequent(nums []int, k int) []int {
cnt := map[int]int{}
for _, x := range nums {
cnt[x]++
}
items := make([][2]int, 0, len(cnt))
for x, c := range cnt {
items = append(items, [2]int{x, c})
}
lo, hi, t := 0, len(items)-1, k-1
for lo < hi {
p := items[(lo+hi)/2][1]
lt, i, gt := lo, lo, hi
for i <= gt {
c := items[i][1]
if c > p {
items[lt], items[i] = items[i], items[lt]
lt++
i++
} else if c < p {
items[gt], items[i] = items[i], items[gt]
gt--
} else {
i++
}
}
if t < lt {
hi = lt - 1
} else if t > gt {
lo = gt + 1
} else {
break
}
}
res := make([]int, k)
for j := 0; j < k; j++ {
res[j] = items[j][0]
}
return res
}var topKFrequent = function(nums, k) {
const cnt = new Map();
for (const x of nums) cnt.set(x, (cnt.get(x) || 0) + 1);
const items = [...cnt];
let lo = 0, hi = items.length - 1;
const t = k - 1;
while (lo < hi) {
const p = items[(lo + hi) >> 1][1];
let lt = lo, i = lo, gt = hi;
while (i <= gt) {
const c = items[i][1];
if (c > p) {
[items[lt], items[i]] = [items[i], items[lt]];
lt++;
i++;
} else if (c < p) {
[items[gt], items[i]] = [items[i], items[gt]];
gt--;
} else {
i++;
}
}
if (t < lt) hi = lt - 1;
else if (t > gt) lo = gt + 1;
else break;
}
return items.slice(0, k).map(([x]) => x);
};function topKFrequent(nums: number[], k: number): number[] {
const cnt = new Map<number, number>();
for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
const items: [number, number][] = [...cnt];
let lo = 0, hi = items.length - 1;
const t = k - 1;
while (lo < hi) {
const p = items[(lo + hi) >> 1][1];
let lt = lo, i = lo, gt = hi;
while (i <= gt) {
const c = items[i][1];
if (c > p) {
[items[lt], items[i]] = [items[i], items[lt]];
lt++;
i++;
} else if (c < p) {
[items[gt], items[i]] = [items[i], items[gt]];
gt--;
} else {
i++;
}
}
if (t < lt) hi = lt - 1;
else if (t > gt) lo = gt + 1;
else break;
}
return items.slice(0, k).map(([x]) => x);
}