347. 前 K 个高频元素（中等）

Blind 75 › 347. 前 K 个高频元素（中等） （第 5 章）
文章工具

题目

给一个整数数组 nums 和一个整数 k，找出出现次数最多的 k 个元素，返回顺序随意。

换句话说：先统计每个数出现的频次，再取频次最高的 k 个值；边界处频次并列时，题目保证选出的答案集合唯一。

自造示例：nums = [7,7,7,8,9,9], k = 2 → [7,9]（也可写作 [9,7]，顺序不限）。其中 7 出现 3 次、9 出现 2 次、8 出现 1 次。

约束：数组长度 1 ~ 105；元素值 -104 ~ 104；k 在 1 到不同元素个数之间。

进阶：算法复杂度必须优于 O(n log n)。

思路

一句话：先统计频次，再把“频次”当桶下标，从高频往低频收集 k 个。

最直白的做法：用哈希统计每个数出现几次，然后按频次从大到小排序，取前 k 个。这要 O(n + m log m)（m 是不同元素个数），最坏 m ≈ n 时是 O(n log n)，不满足进阶要求。

稍微改进：用容量为 k 的小顶堆，只保留当前频次最高的 k 个。时间是 O(n log k)，k 较小时已经比排序好；但 k 接近 n 时仍退化成 O(n log n)。

关键观察：任意元素的频次一定落在 0 到 n 之间，频次是范围有限、可以直接当数组下标的整数。所以不必“比较频次再排序”，直接开 n+1 个桶，把元素丢进“频次号桶”，再从 n 逆着扫到 1，先遇到的桶就是高频元素。这正是桶排序 / 计数排序的思想，全程无比较，O(n)。

解法

三步：

  1. 遍历 nums，用哈希表记录 freq[值] = 出现次数。
  2. 建 buckets[0..n]，把每个值放进 buckets[频次]。
  3. 从 f = n 往 1 逆序扫桶，逐个取元素，凑满 k 个即停。

以 nums=[7,7,7,8,9,9], k=2 为例：

元素频次放入的桶
73buckets[3] = [7]
81buckets[1] = [8]
92buckets[2] = [9]

逆序扫描：f=3 取 7（已有 1 个）→ f=2 取 9（已有 2 个，停止）→ 返回 [7,9]。

下图把上面 3 个步骤串成流程，并逐步演示：

347. 前 K 个高频元素（中等） 解法步骤流程图
图① 解法步骤流程图（共 3 步）。
347. 前 K 个高频元素（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 vector<int> topKFrequent(vector<int>& nums, int k) {
 unordered_map<int, int> freq;
 for (int x : nums) {
 ++freq[x];
 }  int n = nums.size();
 vector<vector<int>> buckets(n + 1);
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。