Top K Frequent Elements 高频元素三解法：排序、最小堆与桶排序（LeetCode 347 全解）

Top K Frequent Elements 高频元素三解法：排序、最小堆与桶排序（LeetCode 347 全解）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以 hints/top-k-elements-in-list.md 与 articles/top-k-elements-in-list.md 为骨架，系统讲解 LeetCode 347「前 K 个高频元素」的三种解法：排序法（O(n log n)）、最小堆法（O(n log k)）与桶排序法（O(n)），并结合本仓库 14 种语言的 0347-top-k-frequent-elements 源码实现进行印证。读完你不仅能独立 AC 该题，还能掌握「频率统计 → 按频次取 Top-K」这一面试高频套路，理解何时该选堆、何时该选桶排序。

题目要求：给定整数数组nums与整数k，返回出现频率最高的k个元素，答案顺序不限。例如nums = [1,1,1,2,2,3], k = 2时，返回[1,2]。

前置知识

动手之前，先确认你对以下四个基础工具足够熟悉，它们是本文三种解法的共同基石：

• 哈希表（Hash Map）：用字典对每个数字计数，是「统计频率」的标准手段，所有解法第一步都依赖它；
• 排序（Sorting）：按自定义规则（此处为频率）排序，对应解法一；
• 堆 / 优先队列（Heap / Priority Queue）：用最小堆维护「前 k 个最大频率」，对应解法二；
• 桶排序（Bucket Sort）：用数组下标当桶做计数型排序，对应解法三（也是 hints 推荐的最终目标解法）。

方法一：排序法 —— O(n log n) 的直觉起点

思路

要找「出现最多的 k 个数」，最朴素的想法是：先数清每个数出现几次，再按次数从大到小排序，取前 k 个即可。整体逻辑一句话概括：统计频率 → 按频率排序 → 取前 k 个。

这种方法最容易推理、最不容易写错，是面试时的合格保底答案。

算法步骤

1. 用哈希表统计每个数字的出现频率；
2. 从哈希表中构建[频率, 数字]的键值对列表；
3. 按频率对该列表排序（升序或降序均可，只要最后能取到最高频的 k 个）；
4. 从排序结果的最高频端依次取出k个数字；
5. 返回结果。

代码实现

Python（升序排序后从尾部弹出）：

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = {} for num in nums: count[num] = 1 + count.get(num, 0) arr = [] for num, cnt in count.items(): arr.append([cnt, num]) arr.sort() res = [] while len(res) < k: res.append(arr.pop()[1]) return res

Java（按频率降序比较器）：

public class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) + 1); } List<int[]> arr = new ArrayList<>(); for (Map.Entry<Integer, Integer> entry : count.entrySet()) { arr.add(new int[] {entry.getValue(), entry.getKey()}); } arr.sort((a, b) -> b[0] - a[0]); int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = arr.get(i)[1]; } return res; } }

C++（反向迭代器实现降序）：

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> count; for (int num : nums) { count[num]++; } vector<pair<int, int>> arr; for (const auto& p : count) { arr.push_back({p.second, p.first}); } sort(arr.rbegin(), arr.rend()); vector<int> res; for (int i = 0; i < k; ++i) { res.push_back(arr[i].second); } return res; } };

JavaScript（Object.entries转数组后降序切片）：

class Solution { topKFrequent(nums, k) { const count = {}; for (const num of nums) { count[num] = (count[num] || 0) + 1; } const arr = Object.entries(count).map(([num, freq]) => [ freq, parseInt(num), ]); arr.sort((a, b) => b[0] - a[0]); return arr.slice(0, k).map((pair) => pair[1]); } }

Go（sort.Slice自定义比较）：

func topKFrequent(nums []int, k int) []int { count := make(map[int]int) for _, num := range nums { count[num]++ } arr := make([][2]int, 0, len(count)) for num, cnt := range count { arr = append(arr, [2]int{cnt, num}) } sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] }) res := make([]int, k) for i := 0; i < k; i++ { res[i] = arr[i][1] } return res }

Rust（sort_unstable_by降序后取前 k）：

impl Solution { pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> { let k = k as usize; let mut count = HashMap::new(); for &num in &nums { *count.entry(num).or_insert(0) += 1; } let mut arr: Vec<(i32, i32)> = count.into_iter().map(|(num, cnt)| (cnt, num)).collect(); arr.sort_unstable_by(|a, b| b.0.cmp(&a.0)); arr.iter().take(k).map(|&(_, num)| num).collect() } }

本仓库 javascript/0347-top-k-frequent-elements.js 中topKFrequent即该思路的独立实现（注释标注Time O(NlogN) | Space O(N)）。

复杂度分析

• 时间复杂度：$O(n \log n)$ —— 瓶颈在排序（n为数组长度）；
• 空间复杂度：$O(n)$ —— 哈希表与排序辅助数组。

方法二：最小堆 —— O(n log k) 的经典优化

思路

统计完频率后，我们并不需要给所有元素排序，只需始终维护最大的 k 个频率。最小堆（min-heap）天然适合：堆顶永远是当前堆内最小的元素。我们把(频率, 数字)压入堆，一旦堆的大小超过k就弹出堆顶（即当前最小的频率），这样堆里永远只保留频率最大的k个数字。

算法步骤

1. 用哈希表统计每个数字的出现频率；
2. 创建一个空的最小堆；
3. 遍历哈希表中的每个数字：
   • 将(频率, 数字)压入堆；
   • 若堆大小大于k，弹出一个元素（移除当前最小频率）；
4. 处理完毕后，堆中恰好保存频率最高的k个数字；
5. 依次弹出堆中所有元素，收集其数字得到结果；
6. 返回结果。

代码实现

Python：

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = {} for num in nums: count[num] = 1 + count.get(num, 0) heap = [] for num in count.keys(): heapq.heappush(heap, (count[num], num)) if len(heap) > k: heapq.heappop(heap) res = [] for i in range(k): res.append(heapq.heappop(heap)[1]) return res

Java（PriorityQueue按频率升序，堆顶即最小频率）：

public class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) + 1); } PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]); for (Map.Entry<Integer, Integer> entry : count.entrySet()) { heap.offer(new int[]{entry.getValue(), entry.getKey()}); if (heap.size() > k) { heap.poll(); } } int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = heap.poll()[1]; } return res; } }

C++（greater使priority_queue变为最小堆）：

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> count; for (int num : nums) { count[num]++; } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap; for (auto& entry : count) { heap.push({entry.second, entry.first}); if (heap.size() > k) { heap.pop(); } } vector<int> res; for (int i = 0; i < k; i++) { res.push_back(heap.top().second); heap.pop(); } return res; } };

Go（实现container/heap接口的MinHeap）：

type MinHeap [][2]int func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { return h[i][0] < h[j][0] } func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) } func (h *MinHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[:n-1] return x } func topKFrequent(nums []int, k int) []int { count := make(map[int]int) for _, num := range nums { count[num]++ } minHeap := &MinHeap{} heap.Init(minHeap) for num, freq := range count { heap.Push(minHeap, [2]int{freq, num}) if minHeap.Len() > k { heap.Pop(minHeap) } } res := make([]int, k) for i := k - 1; i >= 0; i-- { res[i] = heap.Pop(minHeap).([2]int)[1] } return res }

Rust（BinaryHeap是最大堆，用Reverse包装实现最小堆语义）：

impl Solution { pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> { let k = k as usize; let mut count = HashMap::new(); for &num in &nums { *count.entry(num).or_insert(0i32) += 1; } let mut heap = BinaryHeap::new(); for (&num, &freq) in &count { heap.push(Reverse((freq, num))); if heap.len() > k { heap.pop(); } } heap.into_iter().map(|Reverse((_, num))| num).collect() } }

本仓库 java/0347-top-k-frequent-elements.java 中的Solution1正是最小堆实现，注释明确标注Time Complexity: O(nlog(k))。

复杂度分析

• 时间复杂度：$O(n \log k)$ —— 每个数字至多经历一次压堆、一次弹堆，堆操作代价为 $O(\log k)$；
• 空间复杂度：$O(n + k)$ —— 哈希表 $O(n)$，堆最多容纳 $k$ 个元素。

其中n为数组长度，k为要求返回的高频元素个数。

方法三：桶排序 —— O(n) 的最终答案

思路

hints 文件给出的推荐方向是：aim for O(n) time and O(n) space，并提示「能否想出一个按频率分组数字的算法？」「使用桶排序创建 n 个桶，按 1 到 n 的频率把数字分组，然后从 n 到 1 从桶中取出前 k 个数字」。

关键洞察在于：数组里每个数字的出现次数最多不会超过数组长度 n。因此可以建立一个长度为n + 1的列表freq，用下标表示频率，下标i处存放所有恰好出现i次的数字：

• 出现1次的数字放入freq[1]；
• 出现2次的数字放入freq[2]；
• ……以此类推。

分组完成后，从最高频率n向下扫描到1，依次收集桶里的数字，直到集满k个。整个过程没有对元素做全局排序，而是直接「跳到」高频桶，因此达到线性时间。

算法步骤

1. 用哈希表统计每个数字的出现频率；
2. 创建分组列表freq，其中freq[i]存放恰好出现i次的数字（共n + 1个桶）；
3. 遍历哈希表，把每个数字加入freq[频率]对应桶；
4. 初始化空结果列表；
5. 从最大可能频率n向下循环到1：
   • 依次把freq[i]中的数字加入结果；
   • 一旦结果集满k个，立即返回。

代码实现

Python：

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = {} freq = [[] for i in range(len(nums) + 1)] for num in nums: count[num] = 1 + count.get(num, 0) for num, cnt in count.items(): freq[cnt].append(num) res = [] for i in range(len(freq) - 1, 0, -1): for num in freq[i]: res.append(num) if len(res) == k: return res

Java（泛型数组桶，注意每个桶先初始化ArrayList）：

public class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); List<Integer>[] freq = new List[nums.length + 1]; for (int i = 0; i < freq.length; i++) { freq[i] = new ArrayList<>(); } for (int n : nums) { count.put(n, count.getOrDefault(n, 0) + 1); } for (Map.Entry<Integer, Integer> entry : count.entrySet()) { freq[entry.getValue()].add(entry.getKey()); } int[] res = new int[k]; int index = 0; for (int i = freq.length - 1; i > 0 && index < k; i--) { for (int n : freq[i]) { res[index++] = n; if (index == k) { return res; } } } return res; } }

C++（vector<vector<int>>天然支持动态桶）：

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> count; vector<vector<int>> freq(nums.size() + 1); for (int n : nums) { count[n] = 1 + count[n]; } for (const auto& entry : count) { freq[entry.second].push_back(entry.first); } vector<int> res; for (int i = freq.size() - 1; i > 0; --i) { for (int n : freq[i]) { res.push_back(n); if (res.size() == k) { return res; } } } return res; } };

JavaScript：

class Solution { topKFrequent(nums, k) { const count = {}; const freq = Array.from({ length: nums.length + 1 }, () => []); for (const n of nums) { count[n] = (count[n] || 0) + 1; } for (const n in count) { freq[count[n]].push(parseInt(n)); } const res = []; for (let i = freq.length - 1; i > 0; i--) { for (const n of freq[i]) { res.push(n); if (res.length === k) { return res; } } } } }

Go：

func topKFrequent(nums []int, k int) []int { count := make(map[int]int) freq := make([][]int, len(nums)+1) for _, num := range nums { count[num]++ } for num, cnt := range count { freq[cnt] = append(freq[cnt], num) } res := []int{} for i := len(freq) - 1; i > 0; i-- { for _, num := range freq[i] { res = append(res, num) if len(res) == k { return res } } } return res }

Rust：

impl Solution { pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> { let k = k as usize; let mut count = HashMap::new(); let mut freq = vec![vec![]; nums.len() + 1]; for &num in &nums { *count.entry(num).or_insert(0usize) += 1; } for (&num, &cnt) in &count { freq[cnt].push(num); } let mut res = Vec::new(); for i in (1..freq.len()).rev() { for &num in &freq[i] { res.push(num); if res.len() == k { return res; } } } res } }

复杂度分析

• 时间复杂度：$O(n)$ —— 统计频率 $O(n)$，分桶 $O(n)$，从高到低收集最多遍历全部桶与元素，合计仍为 $O(n)$；
• 空间复杂度：$O(n)$ —— 哈希表与n + 1个桶。

仓库源码印证：14 种语言的实现对照

本题对应仓库题目编号0347 - Top K Frequent Elements（见 README.md 的完成度表格），当前仓库在c、cpp、csharp、dart、go、java、javascript、kotlin、python、ruby、rust、scala、swift、typescript共 14 个目录下均提供了实现，与本文三种思路一一对应：

两点值得注意的细节：

1. C 语言实现（c/0347-top-k-frequent-elements.c）受题目值域约束（-10^4 <= nums[i] <= 10^4），采用固定大小hash[20001]数组配合nums[i] + 10000偏移完成计数，再用qsort排序——这是无内置哈希表语言下的典型替代方案；
2. Java 的Solution2与 Rust 实现展示了一种未在本文详述的进阶思路：QuickSelect（Hoare 选择算法），期望复杂度同样为 $O(n)$（最坏 $O(n^2)$）。它通过不断分区把「第 k 大频率」的元素放到正确位置，省去额外桶数组，是桶排序之外的另一种线性期望解法。

常见陷阱

陷阱一：错用最大堆

维护前k个高频元素时，应该用大小为 k 的最小堆：堆顶是最小频率，堆超容时弹出它即可，保证堆内始终是最大的 k 个频率。若误用最大堆，则必须把所有元素都存进堆，最后再弹出 k 次，复杂度退化为 $O(n \log n)$，且空间占用更大。最小堆方案在任何时刻只保留 k 个最大频率，是最优的堆式做法。

陷阱二：忽略相同频率的并列情况

当多个数字频率相同时，它们出现在结果中的先后顺序可能不确定。题目通常接受任意合法顺序，但部分实现会隐式假设某种顺序，导致在并列频率时行为不稳定甚至出错。请确保比较函数能优雅处理频率相等的情形（例如本文所有实现都不依赖并列时的内部顺序）。

陷阱三：桶排序的下标越界（Off-By-One）

桶排序中，频率的取值范围是1到n（数组长度），因此需要n + 1个桶（下标0到n）。最常见的错误是只分配n个桶，当某个元素出现n次时（例如nums = [1,1,1]），访问freq[n]就会越界。务必分配len(nums) + 1个桶，以容纳所有可能的频率。

三种解法对比与选型建议

选型建议：面试时先讲排序法建立信任，再讲最小堆体现对「Top-K 问题」的套路理解，最后用桶排序给出 $O(n)$ 的终极答案并说明「频率上界为 n」这一关键洞察。三者共用「哈希表统计频率」的第一步，代码之间迁移成本极低；后续遇到「前 K 大/小」「第 K 大」等变体题目时，最小堆与 QuickSelect 的思路可直接复用。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode