题目描述给定一个整数数组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]解题思路总览思路时间复杂度空间复杂度适用场景排序后统计O(n log n)O(n)简单直接容易想到堆排序O(n log k)O(n)TopK 经典解法桶排序O(n)O(n)本题最优解快速选择O(n)O(n)需要部分排序时算法一排序后统计思路统计每个元素的出现频率然后对频率进行排序。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;for(intnum:nums){cnt[num];}// 将 map 转为 vector 并按频率降序排序vectorpairint,intvec(cnt.begin(),cnt.end());sort(vec.begin(),vec.end(),[](constpairint,inta,constpairint,intb){returna.secondb.second;});vectorintans;for(inti0;ik;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]复杂度分析复杂度分析时间复杂度O(n log n)- 统计频率O(n)- 排序 n 个不同元素O(n log n)空间复杂度O(n)-cnt哈希表O(n)-vec数组O(n)算法二堆排序TopK 经典解法思路维护一个大小为 k 的小根堆遍历频率数组保留出现频率最高的 k 个元素。小根堆的性质堆顶是最小元素每次插入新元素时会把最小元素挤到堆顶堆大小超过 k 时弹出。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;for(intnum:nums){cnt[num];}// 小根堆pair(频率, 元素)频率小的在堆顶priority_queuepairint,int,vectorpairint,int,greaterpairint,intpq;for(auto[num,freq]:cnt){pq.push({freq,num});if(pq.size()k){pq.pop();// 弹出频率最小的}}vectorintans;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)], size1 k不弹出 | | 遍历 (2,2): pq[(2,2),(3,1)], size2 k不弹出 | | 遍历 (3,1): pq[(1,3),(3,1),(2,2)], size3 k弹出堆顶 | | 弹出 (1,3) -- pq[(2,2),(3,1)] | ------------------------------------------------------------- 第三步取出堆中所有元素 ------------------------------------------------------------- | ans [2, 1] (顺序无关) | ------------------------------------------------------------- 输出: [1,2]复杂度分析复杂度分析时间复杂度O(n log k)- 统计频率O(n)- 遍历 n 个不同元素每次入堆 O(log k)最多 n 次- 弹出 n-k 次每次 O(log k)空间复杂度O(n)-cnt哈希表O(n)- 堆最多 k 个元素O(k)算法三桶排序本题最优解思路出现次数的范围是 [1, n]直接用下标对应频率创建桶数组。桶的下标表示出现次数每个桶里存放出现该次数的所有元素。从高频率向低频率收集。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;intmax_cnt0;for(intnum:nums){cnt[num];max_cntmax(max_cnt,cnt[num]);}vectorvectorintbuckets(max_cnt1);for(auto[x,c]:cnt){buckets[c].push_back(x);}vectorintans;for(intimax_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]复杂度分析复杂度分析时间复杂度O(n)- 统计频率O(n)- 入桶O(n)- 遍历桶最坏 O(n)所有元素在同一桶空间复杂度O(n)-cnt哈希表O(n)-buckets桶数组O(n)算法四快速选择基于 Partition思路利用快速排序的 Partition 思想。先统计频率然后基于频率对元素进行划分。第 n-k 个位置从小到大第 k 个的左边都是频率大于等于它的元素。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;for(intnum:nums){cnt[num];}// 将哈希表转为 vectorvectorpairint,intvec;for(auto[num,freq]:cnt){vec.push_back({num,freq});}intnvec.size();inttargetn-k;// 要找到第 target 小的元素// 快速选择random_shuffle(vec.begin(),vec.end());intleft0,rightn-1;while(leftright){intpivotpartition(vec,left,right);if(pivottarget){break;}elseif(pivottarget){leftpivot1;}else{rightpivot-1;}}vectorintans;for(intitarget;in;i){ans.push_back(vec[i].first);}returnans;}private:intpartition(vectorpairint,intvec,intleft,intright){intpivot_freqvec[right].second;intileft;for(intjleft;jright;j){if(vec[j].secondpivot_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)], left0, right2 | | pivot vec[2] (3,1), i0 | | j0: vec[0](1,3) pivot, 不动 | | j1: vec[1](2,2) pivot, 不动 | | 交换 vec[0] 和 vec[2]: vec [(3,1), (2,2), (1,3)] | | 返回 i0 | | pivot0 target1, left1 | ------------------------------------------------------------- 第三步继续 Partition ------------------------------------------------------------- | vec [(3,1), (2,2), (1,3)], left1, right2 | | pivot vec[2] (1,3), i1 | | j1: vec[1](2,2) pivot, 不动 | | 交换 vec[1] 和 vec[2]: vec [(3,1), (1,3), (2,2)] | | 返回 i1 | | pivot1 target1, 停止 | ------------------------------------------------------------- 第四步取第 target1 之后的元素 ------------------------------------------------------------- | ans [(1,3), (2,2)] 的 first -- [1, 2] | ------------------------------------------------------------- 输出: [1,2]复杂度分析复杂度分析时间复杂度O(n)平均情况- 统计频率O(n)- 每次 Partition O(n)递归深度 O(log n)- 最坏情况 O(n^2)数据有序时空间复杂度O(n)-cnt哈希表O(n)-vec数组O(n)- 递归栈深度 O(log n)复杂度对比总结思路平均时间最坏时间空间稳定性排序后统计O(n log n)O(n log n)O(n)稳定堆排序O(n log k)O(n log k)O(n)不稳定桶排序O(n)O(n)O(n)不稳定快速选择O(n)O(n^2)O(n)不稳定各算法适用场景算法适用场景排序后统计数据量小简单直接容易实现堆排序数据量大k 较小TopK 经典场景桶排序频率范围确定本题最优快速选择需要部分排序不需要维护额外数据结构面试追问 FAQ问题回答为什么用unordered_map而不是mapunordered_map平均 O(1)map需要 O(log n)堆排序为什么用小根堆而不是大根堆小根堆堆顶最小插入 O(log k)弹出后仍满足堆性质桶排序适用于什么场景数据范围确定且相对集中时如频率统计、计数排序快速选择最坏情况如何避免随机打乱数组或用三数取中选 pivot如果 k1 但有多个频率相同的元素怎么办返回任意一个都可以题目允许任意顺序如何处理负数unordered_map原生支持负数键不影响相关题目题目难度核心点692. 前K个高频单词中等多元素比较规则需按字典序二次排序703. 数据流中的第K大元素简单堆的经典应用数据流场景215. 数组中的第K个最大元素中等QuickSelect 或堆排序347. 前K个高频元素中等桶排序最优频率统计总结项目内容最优解桶排序 O(n) 时间、O(n) 空间核心思想用桶下标直接对应出现次数省去堆关键技巧频率范围 [1, n] 确定可用下标直接寻址面试建议优先给出桶排序能想到堆排序是加分项
【力扣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]解题思路总览思路时间复杂度空间复杂度适用场景排序后统计O(n log n)O(n)简单直接容易想到堆排序O(n log k)O(n)TopK 经典解法桶排序O(n)O(n)本题最优解快速选择O(n)O(n)需要部分排序时算法一排序后统计思路统计每个元素的出现频率然后对频率进行排序。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;for(intnum:nums){cnt[num];}// 将 map 转为 vector 并按频率降序排序vectorpairint,intvec(cnt.begin(),cnt.end());sort(vec.begin(),vec.end(),[](constpairint,inta,constpairint,intb){returna.secondb.second;});vectorintans;for(inti0;ik;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]复杂度分析复杂度分析时间复杂度O(n log n)- 统计频率O(n)- 排序 n 个不同元素O(n log n)空间复杂度O(n)-cnt哈希表O(n)-vec数组O(n)算法二堆排序TopK 经典解法思路维护一个大小为 k 的小根堆遍历频率数组保留出现频率最高的 k 个元素。小根堆的性质堆顶是最小元素每次插入新元素时会把最小元素挤到堆顶堆大小超过 k 时弹出。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;for(intnum:nums){cnt[num];}// 小根堆pair(频率, 元素)频率小的在堆顶priority_queuepairint,int,vectorpairint,int,greaterpairint,intpq;for(auto[num,freq]:cnt){pq.push({freq,num});if(pq.size()k){pq.pop();// 弹出频率最小的}}vectorintans;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)], size1 k不弹出 | | 遍历 (2,2): pq[(2,2),(3,1)], size2 k不弹出 | | 遍历 (3,1): pq[(1,3),(3,1),(2,2)], size3 k弹出堆顶 | | 弹出 (1,3) -- pq[(2,2),(3,1)] | ------------------------------------------------------------- 第三步取出堆中所有元素 ------------------------------------------------------------- | ans [2, 1] (顺序无关) | ------------------------------------------------------------- 输出: [1,2]复杂度分析复杂度分析时间复杂度O(n log k)- 统计频率O(n)- 遍历 n 个不同元素每次入堆 O(log k)最多 n 次- 弹出 n-k 次每次 O(log k)空间复杂度O(n)-cnt哈希表O(n)- 堆最多 k 个元素O(k)算法三桶排序本题最优解思路出现次数的范围是 [1, n]直接用下标对应频率创建桶数组。桶的下标表示出现次数每个桶里存放出现该次数的所有元素。从高频率向低频率收集。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;intmax_cnt0;for(intnum:nums){cnt[num];max_cntmax(max_cnt,cnt[num]);}vectorvectorintbuckets(max_cnt1);for(auto[x,c]:cnt){buckets[c].push_back(x);}vectorintans;for(intimax_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]复杂度分析复杂度分析时间复杂度O(n)- 统计频率O(n)- 入桶O(n)- 遍历桶最坏 O(n)所有元素在同一桶空间复杂度O(n)-cnt哈希表O(n)-buckets桶数组O(n)算法四快速选择基于 Partition思路利用快速排序的 Partition 思想。先统计频率然后基于频率对元素进行划分。第 n-k 个位置从小到大第 k 个的左边都是频率大于等于它的元素。代码classSolution{public:vectorinttopKFrequent(vectorintnums,intk){unordered_mapint,intcnt;for(intnum:nums){cnt[num];}// 将哈希表转为 vectorvectorpairint,intvec;for(auto[num,freq]:cnt){vec.push_back({num,freq});}intnvec.size();inttargetn-k;// 要找到第 target 小的元素// 快速选择random_shuffle(vec.begin(),vec.end());intleft0,rightn-1;while(leftright){intpivotpartition(vec,left,right);if(pivottarget){break;}elseif(pivottarget){leftpivot1;}else{rightpivot-1;}}vectorintans;for(intitarget;in;i){ans.push_back(vec[i].first);}returnans;}private:intpartition(vectorpairint,intvec,intleft,intright){intpivot_freqvec[right].second;intileft;for(intjleft;jright;j){if(vec[j].secondpivot_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)], left0, right2 | | pivot vec[2] (3,1), i0 | | j0: vec[0](1,3) pivot, 不动 | | j1: vec[1](2,2) pivot, 不动 | | 交换 vec[0] 和 vec[2]: vec [(3,1), (2,2), (1,3)] | | 返回 i0 | | pivot0 target1, left1 | ------------------------------------------------------------- 第三步继续 Partition ------------------------------------------------------------- | vec [(3,1), (2,2), (1,3)], left1, right2 | | pivot vec[2] (1,3), i1 | | j1: vec[1](2,2) pivot, 不动 | | 交换 vec[1] 和 vec[2]: vec [(3,1), (1,3), (2,2)] | | 返回 i1 | | pivot1 target1, 停止 | ------------------------------------------------------------- 第四步取第 target1 之后的元素 ------------------------------------------------------------- | ans [(1,3), (2,2)] 的 first -- [1, 2] | ------------------------------------------------------------- 输出: [1,2]复杂度分析复杂度分析时间复杂度O(n)平均情况- 统计频率O(n)- 每次 Partition O(n)递归深度 O(log n)- 最坏情况 O(n^2)数据有序时空间复杂度O(n)-cnt哈希表O(n)-vec数组O(n)- 递归栈深度 O(log n)复杂度对比总结思路平均时间最坏时间空间稳定性排序后统计O(n log n)O(n log n)O(n)稳定堆排序O(n log k)O(n log k)O(n)不稳定桶排序O(n)O(n)O(n)不稳定快速选择O(n)O(n^2)O(n)不稳定各算法适用场景算法适用场景排序后统计数据量小简单直接容易实现堆排序数据量大k 较小TopK 经典场景桶排序频率范围确定本题最优快速选择需要部分排序不需要维护额外数据结构面试追问 FAQ问题回答为什么用unordered_map而不是mapunordered_map平均 O(1)map需要 O(log n)堆排序为什么用小根堆而不是大根堆小根堆堆顶最小插入 O(log k)弹出后仍满足堆性质桶排序适用于什么场景数据范围确定且相对集中时如频率统计、计数排序快速选择最坏情况如何避免随机打乱数组或用三数取中选 pivot如果 k1 但有多个频率相同的元素怎么办返回任意一个都可以题目允许任意顺序如何处理负数unordered_map原生支持负数键不影响相关题目题目难度核心点692. 前K个高频单词中等多元素比较规则需按字典序二次排序703. 数据流中的第K大元素简单堆的经典应用数据流场景215. 数组中的第K个最大元素中等QuickSelect 或堆排序347. 前K个高频元素中等桶排序最优频率统计总结项目内容最优解桶排序 O(n) 时间、O(n) 空间核心思想用桶下标直接对应出现次数省去堆关键技巧频率范围 [1, n] 确定可用下标直接寻址面试建议优先给出桶排序能想到堆排序是加分项
