【力扣100题】92.前 K 个高频元素

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路总览

算法一：排序后统计

思路

统计每个元素的出现频率，然后对频率进行排序。

代码

classSolution{public:vector<int>topKFrequent(vector<int>&nums,intk){unordered_map<int,int>cnt;for(intnum:nums){cnt[num]++;}// 将 map 转为 vector 并按频率降序排序vector<pair<int,int>>vec(cnt.begin(),cnt.end());sort(vec.begin(),vec.end(),[](constpair<int,int>&a,constpair<int,int>&b){returna.second>b.second;});vector<int>ans;for(inti=0;i<k;i++){ans.push_back(vec[i].first);}returnans;}};

算法流程

输入: nums = [1,1,1,2,2,3], k = 2 第一步：统计频率 +-------------------------------------------------------------+ | num | 1 | 2 | 3 | | | cnt | 3 | 2 | 1 | | +-------------------------------------------------------------+ 第二步：转成 vector 并排序 +-------------------------------------------------------------+ | vec = [(1,3), (2,2), (3,1)] --按 second 降序--> [(1,3),(2,2),(3,1)] | +-------------------------------------------------------------+ 第三步：取前 k 个 +-------------------------------------------------------------+ | 取前 2 个: ans = [1, 2] | +-------------------------------------------------------------+ 输出: [1,2]

复杂度分析

算法二：堆排序（TopK 经典解法）

思路

维护一个大小为 k 的小根堆，遍历频率数组，保留出现频率最高的 k 个元素。

小根堆的性质：堆顶是最小元素，每次插入新元素时，会把最小元素"挤"到堆顶，堆大小超过 k 时弹出。

代码

classSolution{public:vector<int>topKFrequent(vector<int>&nums,intk){unordered_map<int,int>cnt;for(intnum:nums){cnt[num]++;}// 小根堆：pair(频率, 元素)，频率小的在堆顶priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;for(auto&[num,freq]:cnt){pq.push({freq,num});if(pq.size()>k){pq.pop();// 弹出频率最小的}}vector<int>ans;while(!pq.empty()){ans.push_back(pq.top().second);pq.pop();}returnans;}};

算法流程

输入: nums = [1,1,1,2,2,3], k = 2 第一步：统计频率 +-------------------------------------------------------------+ | num | 1 | 2 | 3 | | | cnt | 3 | 2 | 1 | | +-------------------------------------------------------------+ 第二步：遍历哈希表，入堆并维护大小为 k 的小根堆 +-------------------------------------------------------------+ | 遍历 (1,3): pq=[(3,1)], size=1 <= k，不弹出 | | 遍历 (2,2): pq=[(2,2),(3,1)], size=2 <= k，不弹出 | | 遍历 (3,1): pq=[(1,3),(3,1),(2,2)], size=3 > k，弹出堆顶 | | 弹出 (1,3) --> pq=[(2,2),(3,1)] | +-------------------------------------------------------------+ 第三步：取出堆中所有元素 +-------------------------------------------------------------+ | ans = [2, 1] (顺序无关) | +-------------------------------------------------------------+ 输出: [1,2]

复杂度分析

算法三：桶排序（本题最优解）

思路

出现次数的范围是 [1, n]，直接用下标对应频率，创建桶数组。桶的下标表示出现次数，每个桶里存放出现该次数的所有元素。从高频率向低频率收集。

代码

classSolution{public:vector<int>topKFrequent(vector<int>&nums,intk){unordered_map<int,int>cnt;intmax_cnt=0;for(intnum:nums){cnt[num]++;max_cnt=max(max_cnt,cnt[num]);}vector<vector<int>>buckets(max_cnt+1);for(auto&[x,c]:cnt){buckets[c].push_back(x);}vector<int>ans;for(inti=max_cnt;ans.size()<k;i--){ans.insert(ans.end(),buckets[i].begin(),buckets[i].end());}returnans;}};

算法流程

输入: nums = [1,1,1,2,2,3], k = 2 第一步：统计频率 +-------------------------------------------------------------+ | num | 1 | 2 | 3 | | | cnt | 3 | 2 | 1 | | | max_cnt = 3 | +-------------------------------------------------------------+ 第二步：创建桶并放入元素（桶编号 = 出现次数） +-------------------------------------------------------------+ | bucket[0] | bucket[1] | bucket[2] | bucket[3] | | | [] | [3] | [2] | [1] | | +-------------------------------------------------------------+ 第三步：从高到低遍历桶，收集 k 个元素 +-------------------------------------------------------------+ | i = 3: bucket[3] = [1] --> ans = [1] | | i = 2: bucket[2] = [2] --> ans = [1, 2] | | ans.size() = 2 == k，停止遍历 | +-------------------------------------------------------------+ 输出: [1,2]

复杂度分析

算法四：快速选择（基于 Partition）

思路

利用快速排序的 Partition 思想。先统计频率，然后基于频率对元素进行划分。第 n-k 个位置（从小到大第 k 个）的左边都是频率大于等于它的元素。

代码

classSolution{public:vector<int>topKFrequent(vector<int>&nums,intk){unordered_map<int,int>cnt;for(intnum:nums){cnt[num]++;}// 将哈希表转为 vectorvector<pair<int,int>>vec;for(auto&[num,freq]:cnt){vec.push_back({num,freq});}intn=vec.size();inttarget=n-k;// 要找到第 target 小的元素// 快速选择random_shuffle(vec.begin(),vec.end());intleft=0,right=n-1;while(left<=right){intpivot=partition(vec,left,right);if(pivot==target){break;}elseif(pivot<target){left=pivot+1;}else{right=pivot-1;}}vector<int>ans;for(inti=target;i<n;i++){ans.push_back(vec[i].first);}returnans;}private:intpartition(vector<pair<int,int>>&vec,intleft,intright){intpivot_freq=vec[right].second;inti=left;for(intj=left;j<right;j++){if(vec[j].second<pivot_freq){swap(vec[i],vec[j]);i++;}}swap(vec[i],vec[right]);returni;}};

算法流程

输入: nums = [1,1,1,2,2,3], k = 2 第一步：统计频率 +-------------------------------------------------------------+ | vec = [(1,3), (2,2), (3,1)] | | n = 3, target = 3 - 2 = 1 | +-------------------------------------------------------------+ 第二步：快速选择 Partition +-------------------------------------------------------------+ | 初始: vec = [(1,3), (2,2), (3,1)], left=0, right=2 | | pivot = vec[2] = (3,1), i=0 | | j=0: vec[0]=(1,3) >= pivot, 不动 | | j=1: vec[1]=(2,2) >= pivot, 不动 | | 交换 vec[0] 和 vec[2]: vec = [(3,1), (2,2), (1,3)] | | 返回 i=0 | | pivot=0 < target=1, left=1 | +-------------------------------------------------------------+ 第三步：继续 Partition +-------------------------------------------------------------+ | vec = [(3,1), (2,2), (1,3)], left=1, right=2 | | pivot = vec[2] = (1,3), i=1 | | j=1: vec[1]=(2,2) >= pivot, 不动 | | 交换 vec[1] 和 vec[2]: vec = [(3,1), (1,3), (2,2)] | | 返回 i=1 | | pivot=1 == target=1, 停止 | +-------------------------------------------------------------+ 第四步：取第 target=1 之后的元素 +-------------------------------------------------------------+ | ans = [(1,3), (2,2)] 的 first --> [1, 2] | +-------------------------------------------------------------+ 输出: [1,2]

复杂度分析

复杂度对比总结

各算法适用场景

面试追问 FAQ

相关题目

总结