前 K 个高频元素Top K Frequent Elements排序、最小堆与桶排序三种解法全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文以 LeetCode 347「前 K 个高频元素」Top K Frequent Elements为核心系统拆解该问题的三类主流解法基于频率统计的排序法、维护大小为 k 的最小堆、以及利用频率上界的桶排序。仓库 leetcode 在python、java、cpp、go等十余个语言目录下均收录了本题的完整实现如 python/0347-top-k-frequent-elements.py、java/0347-top-k-frequent-elements.java、cpp/0347-top-k-frequent-elements.cpp阅读完本文你将掌握三种解法的推导思路、多语言代码模板、复杂度对比以及快速选择Quickselect等仓库内的进阶实现可直接迁移到面试与日常工程场景。问题定义与仓库对应实现给定一个整数数组nums和一个整数k返回其中出现频率最高的前k个元素。示例nums [1,1,1,2,2,3], k 2→ 返回[1, 2]示例nums [1], k 1→ 返回[1]该题在仓库中以0347-top-k-frequent-elements命名覆盖了 14 种语言包括 C 语言、C、C#、Dart、Go、Java、JavaScript、Kotlin、Python、Ruby、Rust、Scala、Swift 与 TypeScript可以作为多语言对照学习与自测的素材。前置知识在动手实现前需要熟悉以下四个基础工具哈希表Hash Map用字典高效统计每个元素的出现次数是三种解法的共同第一步排序Sorting按自定义规则本题为频率对元素排序堆 / 优先队列Heap / Priority Queue利用最小堆在遍历过程中始终维护前k个最高频元素桶排序Bucket Sort用数组下标充当频率桶实现基于计数的线性时间排序。解法一排序直觉要找出前k个最高频元素首先必须知道每个数字出现了多少次。统计完频率后把去重后的数字按出现次数排序频率最高的数字自然排在末尾取最后k个即可。整个思路可以一句话概括统计频率 → 按频率排序 → 取前 k 个。算法步骤用哈希表记录每个数字出现的次数从哈希表构造[频率, 数字]形式的列表按频率对该列表升序排序初始化空结果列表反复从有序列表末尾弹出频率最高的元素并加入结果直到结果中包含k个元素为止返回结果列表。多语言实现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 respublic class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer count new HashMap(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) 1); } Listint[] arr new ArrayList(); for (Map.EntryInteger, 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; } }class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int count; for (int num : nums) { count[num]; } vectorpairint, int arr; for (const auto p : count) { arr.push_back({p.second, p.first}); } sort(arr.rbegin(), arr.rend()); vectorint res; for (int i 0; i k; i) { res.push_back(arr[i].second); } return res; } };class Solution { /** * param {number[]} nums * param {number} k * return {number[]} */ 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]); } }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 }impl Solution { pub fn top_k_frequent(nums: Veci32, k: i32) - Veci32 { 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() } }说明Python 代码在 LeetCode 环境中List与heapq等已隐式导入本地运行需自行补充from typing import List等导入语句。其余语言C#、Kotlin、Swift 等的排序实现可对照 csharp/0347-top-k-frequent-elements.cs 等文件查看。复杂度分析时间复杂度$O(n \log n)$主要开销在排序$n$ 为数组长度空间复杂度$O(n)$存储频率表与排序副本解法二最小堆Min-Heap直觉统计完频率之后我们希望只记住前k个最高频元素而不是排序全部元素。最小堆天然满足这个需求——它始终把最小元素放在堆顶。做法是把(频率, 数字)压入堆中一旦堆的大小超过k就弹出一个弹出的恰好是当前堆里频率最小的元素。于是堆中永远只保留频率最高的k个元素遍历完频率表后直接取出即可。算法步骤构建频率表统计每个数字出现的次数创建一个空的最小堆遍历频率表中的每个数字将(频率, 数字)压入堆若堆的大小超过k弹出堆顶频率最小的元素处理完所有数字后堆中恰好是前k个最高频元素依次弹出堆中所有元素收集其数字组成结果列表返回结果。多语言实现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 respublic class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer count new HashMap(); for (int num : nums) { count.put(num, count.getOrDefault(num, 0) 1); } PriorityQueueint[] heap new PriorityQueue((a, b) - a[0] - b[0]); for (Map.EntryInteger, 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; } }class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int count; for (int num : nums) { count[num]; } priority_queuepairint, int, vectorpairint, int, greaterpairint, int heap; for (auto entry : count) { heap.push({entry.second, entry.first}); if (heap.size() k) { heap.pop(); } } vectorint res; for (int i 0; i k; i) { res.push_back(heap.top().second); heap.pop(); } return res; } };class Solution { /** * param {number[]} nums * param {number} k * return {number[]} */ topKFrequent(nums, k) { const count {}; for (const num of nums) { count[num] (count[num] || 0) 1; } const heap new MinPriorityQueue((x) x[1]); for (const [num, cnt] of Object.entries(count)) { heap.enqueue([num, cnt]); if (heap.size() k) heap.dequeue(); } const res []; for (let i 0; i k; i) { const [num, cnt] heap.dequeue(); res.push(num); } return res; } }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 }impl Solution { pub fn top_k_frequent(nums: Veci32, k: i32) - Veci32 { 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() } }实现细节Python 的heapq默认是最小堆Rust 的BinaryHeap默认是最大堆因此用Reverse((freq, num))包装成伪最小堆来弹出最小值C 用greaterpairint, int构造最小堆JavaScript 使用 LeetCode 环境内置的MinPriorityQueue。Go 需要自行实现container/heap接口Len/Less/Swap/Push/Pop。复杂度分析时间复杂度$O(n \log k)$堆中最多保留 $k$ 个元素每次压入/弹出为 $O(\log k)$空间复杂度$O(n k)$其中 $n$ 为数组长度$k$ 为需要返回的最高频元素个数。解法三桶排序Bucket Sort直觉数组中每个数字出现的次数必然落在1到n数组长度之间这是一个天然的频率上界。据此可以构造一个列表用下标表示频率下标处存放所有出现次数恰好为该下标的数字出现1次的数字放入freq[1]出现2次的数字放入freq[2]依此类推。分组完成后从最高可能频率向下扫描依次收集每个桶里的数字直到集满k个。这样无需对所有元素按频率排序就能直接跳到最高频的那批元素。算法步骤构建频率表统计每个数字出现的次数创建分组列表freq其中freq[i]存放恰好出现i次的数字遍历频率表把每个数字放入对应的freq[frequency]初始化空结果列表从最大可能频率向下循环到1将freq[i]中的每个数字加入结果一旦结果达到k个立即返回。多语言实现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 respublic class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer count new HashMap(); ListInteger[] 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.EntryInteger, 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; } }class Solution { public: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int count; vectorvectorint 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); } vectorint 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; } };class Solution { /** * param {number[]} nums * param {number} k * return {number[]} */ 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; } } } } }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 }impl Solution { pub fn top_k_frequent(nums: Veci32, k: i32) - Veci32 { 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 } }class Solution { func topKFrequent(_ nums: [Int], _ k: Int) - [Int] { var count [Int: Int]() var freq [[Int]](repeating: [], count: nums.count 1) for num in nums { count[num, default: 0] 1 } for (num, cnt) in count { freq[cnt].append(num) } var res [Int]() for i in stride(from: freq.count - 1, through: 1, by: -1) { for num in freq[i] { res.append(num) if res.count k { return res } } } return res } }class Solution { fun topKFrequent(nums: IntArray, k: Int): IntArray { val count HashMapInt, Int() val freq List(nums.size 1) { mutableListOfInt() } for (num in nums) { count[num] count.getOrDefault(num, 0) 1 } for ((num, cnt) in count) { freq[cnt].add(num) } val res mutableListOfInt() for (i in freq.size - 1 downTo 1) { for (num in freq[i]) { res.add(num) if (res.size k) { return res.toIntArray() } } } return res.toIntArray() } }public class Solution { public int[] TopKFrequent(int[] nums, int k) { Dictionaryint, int count new Dictionaryint, int(); Listint[] freq new Listint[nums.Length 1]; for (int i 0; i freq.Length; i) { freq[i] new Listint(); } foreach (int n in nums) { if (count.ContainsKey(n)) { count[n]; } else { count[n] 1; } } foreach (var entry in count){ freq[entry.Value].Add(entry.Key); } int[] res new int[k]; int index 0; for (int i freq.Length - 1; i 0 index k; i--) { foreach (int n in freq[i]) { res[index] n; if (index k) { return res; } } } return res; } }仓库中的 python/0347-top-k-frequent-elements.py、cpp/0347-top-k-frequent-elements.cpp、go/0347-top-k-frequent-elements.go、swift/0347-top-k-frequent-elements.swift 等提交版本正是以桶排序作为最终答案并在 C 版注释中记录了两种方案的复杂度权衡O(n log k)的堆方案 vsO(n)的桶方案。复杂度分析时间复杂度$O(n)$构建频率表 $O(n)$桶的分组与收集均为线性扫描空间复杂度$O(n)$频率表与桶数组仓库中的进阶实现快速选择Quickselect除了文档给出的三种主流解法仓库源码还收录了两种值得学习的进阶实现1. Java 的 Hoare 快速选择java/0347-top-k-frequent-elements.java 中的Solution2它没有对全部元素排序而是对去重后的 key 数组执行部分选择select(keys, map, 0, size - 1, size - k)找到第size - k小的分界点其右侧恰好是频率最高的k个元素。核心是一个修改版的 Hoare 分区partition以map.get(keys[pivot])为基准值划分左右平均时间复杂度 $O(n)$空间 $O(n)$。2. Rust 的递归快速选择rust/0347-top-k-frequent-elements.rsRust 版同样使用快速选择以首元素为基准分区后根据大于等于基准的元素个数与k的大小关系递归地在左半段或右半段继续选择直到恰好找到k个最大频率元素为止。3. C 语言的定长哈希 堆排序c/0347-top-k-frequent-elements.cC 版受限于语言没有内置哈希表采用定长数组hash[20001]下标偏移10000以容纳负数完成计数再把(num, count)填入自定义Heap结构体用qsort按频率降序排序后取前k个。注意返回值需malloc分配、由调用方free()并写入returnSize。这些实现与文档中统计频率 → 筛选 Top-k的主线一脉相承只是把排序全部或堆维护替换为部分选择适合在理解了三种基础解法之后进一步对比学习。常见陷阱Common Pitfalls误用最大堆而非最小堆维护前k个最高频元素时必须使用大小为k的最小堆当堆超过k个元素时弹出堆顶当前最小频率即可保持只留最大 k 个。如果使用最大堆则必须把所有元素全部压入堆中再连续弹出k次——复杂度退化为 $O(n \log n)$而且失去了流式维护的优势。最小堆方案任意时刻都只持有频率最大的k个元素是本题的标准堆解法。忘记处理频率相等的情况当多个数字频率相同时它们在结果中的相对顺序可能不确定。绝大多数题目对同频元素的顺序没有要求任意合法排列都可通过但有些实现会在频率相等时出错或者错误地假设了固定顺序。确保比较函数能优雅处理相等频率——例如 Python 直接对[cnt, num]排序时相等的cnt会继续按num比较这并不会导致错误只是结果顺序与直觉可能不同。桶排序下标的差一错误Off-By-One在桶排序中频率的取值范围是1到n数组长度因此需要n 1个桶下标从0到n。常见错误是只创建n个桶当某个元素恰好出现n次时发生数组越界。务必分配len(nums) 1个桶以覆盖所有可能的频率值。仓库中的各语言实现均严格遵循这一约定例如 Python 的freq [[] for i in range(len(nums) 1)]与 Go 的freq : make([][]int, len(nums)1)。三种解法对比与总结解法时间复杂度空间复杂度适用场景排序$O(n \log n)$$O(n)$实现最简单适合快速写出可运行代码最小堆$O(n \log k)$$O(n k)$数据流式到达、k远小于n时最省时桶排序$O(n)$$O(n)$频率存在明确上界本题为n时最优快速选择平均 $O(n)$$O(n)$期望线性时间不要求频率有界见仓库 Java/Rust 版回到核心主线统计频率 → 按频率筛选前 k 个。三者共享第一步哈希表计数区别仅在第二步的筛选策略——排序法把所有元素排好序再截取堆法只保留k个候选并动态淘汰桶排序则借助频率上界直接线性收集。理解这三条路径的取舍就掌握了Top K类问题的通用思维框架可以轻松迁移到Kth Largest Element、Top K Frequent Words等同类题目。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考