LeetCode347 前K个高频元素解题思路与实现

LeetCode347 前K个高频元素解题思路与实现

题目链接
问题描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例:

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

思路分析

本题要求找出数组中出现频率最高的k个元素，主要解决思路如下：

计数统计：首先需要统计每个元素出现的频率。这里选择unordered_map而非map，因为unordered_map的插入和查找操作时间复杂度为O(1)，而map为O(log n)，且我们不需要对键进行排序。

频率排序：统计完成后，需要对元素按频率进行排序。这里使用优先队列（大顶堆）来实现，它可以帮助我们高效地获取频率最高的元素。

结果提取：从优先队列中取出前k个元素，即为所求结果。

代码实现

class Solution { public: //最开始考虑使用map,但是map是根据first元素进行排序的但是这道题是要对元素出现的次数进行排序，所以使用unordered_map  //然后将unorder_map中的元素在使用优先队列插入，头部的元素就是我们要的元素  vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> num; //放入unordered_map计数  for(auto i : nums) num[i]++; priority_queue<pair<int, int>> q; for(auto i : num) q.emplace(i.second, i.first); vector<int> res; while(k--) { res.push_back(q.top().second); q.pop(); } return res; } };

复杂度分析

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

统计频率：O(n)
构建优先队列：O(n log n)（插入n个元素，每个插入操作O(log n)）
提取k个元素：O(k log n)

空间复杂度：O(n)

哈希表存储频率：O(n)
优先队列存储元素：O(n)
小顶堆优化解法

除了大顶堆实现外，使用小顶堆维护k个高频元素可以进一步优化空间复杂度，尤其适合k值较小的场景。

算法思路
频率统计：使用哈希表统计元素频率
小顶堆维护：只保留k个高频元素，当堆大小超过k时移除频率最小的元素
结果收集：从堆中提取元素并整理结果
代码实现

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { //使用 unordered_map 然后在使用优先队列的小顶堆进行堆前k大的元素进行维护  unordered_map<int, int> map; for(auto i : nums) { map[i]++; } struct a{ bool operator()(const pair<int, int> lhs, const pair<int, int> rhs) const {  return lhs.second > rhs.second; } }; priority_queue<pair<int, int>, vector<pair<int, int>>, a > pri_q; for(auto i = map.begin(); i != map.end(); i++) { pri_q.push(*i); if(pri_q.size() > k)  pri_q.pop(); } // 将优先级队列中的元素加入res  vector<int> res; while(!pri_q.empty()) { res.push_back(pri_q.top().first); pri_q.pop(); } reverse(res.begin(), res.end()); return res; } };

关键优化点
空间优化：堆大小固定为k，空间复杂度降至O(k)
时间优化：堆操作从O(n log n)降至O(n log k)，适合大数据量场景
适用性广：当k远小于n时（如Top 10），性能优势明显
桶排序解法详解

除了优先队列实现外，桶排序是另一种高效解决Top K高频元素问题的方法，时间复杂度可优化至O(n)。

算法思路
频率统计：使用哈希表统计每个元素的出现频率
桶初始化：创建以频率为索引的\"桶数组\"，将元素按频率分类
逆序收集：从最高频率桶开始收集元素，直到获取k个元素
代码实现

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { //基于桶排序的思想，先使用哈希表统计出最大的次数max，然后,开max个数组，将对应数字插入，因为题目说要保证唯一答案，所以桶中元素不用进行排序  unordered_map<int, int> map; int max_num = 0; //先定义一个值为最大，遍历的时候就将最大值找出来  for(auto i : nums) { map[i]++; max_num = max(max_num, map[i]); } // 开max_num + 1个数组  vector<int> vec[max_num+1]; int size = nums.size(); //如果没有元素会越界访问  // for(int i = size ; i > 0; i--)  // {  // vec[map[i]].push_back(i);  // }  for(auto &p : map) { vec[p.second].push_back(p.first); } //从后面的数组开始取数据，取k个，返回  vector<int> ans; for(int i = max_num; i >= 0 && ans.size() < k; i--) { //在哪个位置插入 ，什么元素  ans.insert(ans.end(), vec[i].begin(), vec[i].end()); } return ans; } };

关键优化点
空间换时间：通过桶数组直接映射频率与元素，避免排序操作
边界处理：无需考虑桶为空的情况，直接从高频率向低频率遍历
稳定性保证：题目保证答案唯一，无需处理频率相同元素的排序问题
三种解法对比
方法 时间复杂度 空间复杂度 适用场景
大顶堆 O(n log n) O(n) 数据量较小或k接近n
小顶堆 O(n log k) O(n + k) k远小于n的场景
桶排序 O(n) O(n) 频率分布均匀且已知最大频率
总结与拓展

通过对比三种解法可以发现：

大顶堆实现最直观，适合处理一般规模数据
小顶堆在k值较小时空间效率更优
桶排序在时间效率上最优，但需要预知最大频率值

实际面试中，应根据数据特征灵活选择解法，并能清晰阐述各种方法的优缺点及适用场景。