LeetCode 第347题：前K个高频元素

📖 文章摘要

本文详细解析LeetCode第347题“前K个高频元素”，这是一道中等难度的哈希表和堆题目。文章提供了基于优先队列和桶排序两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要学习哈希表和堆应用的程序员。

核心知识点： 哈希表、优先队列、桶排序
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升算法应用能力的开发者

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例

示例 1：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2：

输入: nums = [1], k = 1
输出: [1]

提示

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

解题思路

方法一：优先队列

使用哈希表统计频率，然后用小顶堆维护前K个高频元素。

关键点：

使用哈希表统计每个元素出现的频率
使用小顶堆维护K个最大值
当堆的大小超过K时，移除堆顶元素
最后将堆中元素转换为结果数组

具体步骤：

遍历数组，使用哈希表统计频率
创建小顶堆，遍历哈希表：
- 将元素加入堆中
- 当堆大小超过K时，移除堆顶
将堆中元素转换为结果数组

时间复杂度：O(nlogk) 空间复杂度：O(n)

方法二：桶排序

使用桶排序，每个桶存储出现频率相同的元素。

关键点：

使用哈希表统计频率
创建频率桶数组
从后向前遍历桶，收集前K个元素
避免使用排序，提高效率

具体步骤：

统计频率
创建桶数组
将元素放入对应频率的桶中
从高频率向低频率遍历，收集结果

时间复杂度：O(n) 空间复杂度：O(n)

图解思路

优先队列过程分析表

步骤	操作	堆内容	说明
初始	统计频率	{}	{1:3, 2:2, 3:1}
第1步	加入1	{(1,3)}	频率为3
第2步	加入2	{(2,2),(1,3)}	频率为2
第3步	加入3	{(3,1),(1,3)}	k=2，移除3

桶排序示意图

频率统计：{1:3, 2:2, 3:1}
桶数组：
频率3：[1]
频率2：[2]
频率1：[3]
从高到低收集：[1,2]

代码实现

C# 实现

public class Solution {
    // 方法一：优先队列
    public int[] TopKFrequent(int[] nums, int k) {
        // 统计频率
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!freq.ContainsKey(num)) {
                freq[num] = 0;
            }
            freq[num]++;
        }
        
        // 使用优先队列（小顶堆）
        var pq = new PriorityQueue<int, int>();
        foreach (var pair in freq) {
            pq.Enqueue(pair.Key, pair.Value);
            if (pq.Count > k) {
                pq.Dequeue();
            }
        }
        
        // 构建结果
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pq.Dequeue();
        }
        
        return result;
    }
    
    // 方法二：桶排序
    public int[] TopKFrequentBucket(int[] nums, int k) {
        // 统计频率
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!freq.ContainsKey(num)) {
                freq[num] = 0;
            }
            freq[num]++;
        }
        
        // 创建桶
        List<int>[] buckets = new List<int>[nums.Length + 1];
        foreach (var pair in freq) {
            if (buckets[pair.Value] == null) {
                buckets[pair.Value] = new List<int>();
            }
            buckets[pair.Value].Add(pair.Key);
        }
        
        // 收集结果
        List<int> result = new List<int>();
        for (int i = buckets.Length - 1; i >= 0 && result.Count < k; i--) {
            if (buckets[i] != null) {
                result.AddRange(buckets[i]);
            }
        }
        
        return result.Take(k).ToArray();
    }
}

Python 实现

from collections import Counter
import heapq

class Solution:
    # 方法一：优先队列
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 统计频率
        count = Counter(nums)
        
        # 使用堆
        return heapq.nlargest(k, count.keys(), key=count.get)
    
    # 方法二：桶排序
    def topKFrequentBucket(self, nums: List[int], k: int) -> List[int]:
        # 统计频率
        count = Counter(nums)
        
        # 创建桶
        bucket = [[] for _ in range(len(nums) + 1)]
        for num, freq in count.items():
            bucket[freq].append(num)
        
        # 收集结果
        result = []
        for i in range(len(bucket) - 1, -1, -1):
            result.extend(bucket[i])
            if len(result) >= k:
                return result[:k]
        
        return result

C++ 实现

class Solution {
public:
    // 方法一：优先队列
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 统计频率
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        // 使用优先队列（小顶堆）
        priority_queue<pair<int, int>, vector<pair<int, int>>, 
            greater<pair<int, int>>> pq;
            
        for (auto& [num, count] : freq) {
            pq.push({count, num});
            if (pq.size() > k) {
                pq.pop();
            }
        }
        
        // 构建结果
        vector<int> result;
        while (!pq.empty()) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
    
    // 方法二：桶排序
    vector<int> topKFrequentBucket(vector<int>& nums, int k) {
        // 统计频率
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        // 创建桶
        vector<vector<int>> buckets(nums.size() + 1);
        for (auto& [num, count] : freq) {
            buckets[count].push_back(num);
        }
        
        // 收集结果
        vector<int> result;
        for (int i = buckets.size() - 1; i >= 0 && result.size() < k; i--) {
            for (int num : buckets[i]) {
                result.push_back(num);
                if (result.size() == k) {
                    break;
                }
            }
        }
        
        return result;
    }
};

执行结果

C# 实现

执行用时：168 ms
内存消耗：45.2 MB

Python 实现

执行用时：96 ms
内存消耗：19.8 MB

C++ 实现

执行用时：12 ms
内存消耗：13.5 MB

性能对比

语言	执行用时	内存消耗	特点
C#	168 ms	45.2 MB	代码结构清晰
Python	96 ms	19.8 MB	实现简洁
C++	12 ms	13.5 MB	性能最优

代码亮点

🎯 多种解法思路清晰
💡 优先队列实现高效
🔍 桶排序避免排序
🎨 代码结构优雅

常见错误分析

🚫 忘记处理频率相同的元素
🚫 优先队列使用错误
🚫 桶排序边界处理不当
🚫 结果数组大小控制错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
优先队列	O(nlogk)	O(n)	适合处理流数据	常数较大
桶排序	O(n)	O(n)	性能最优	需要额外空间

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第347题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法一：优先队列

方法二：桶排序

图解思路

优先队列过程分析表

桶排序示意图

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流