LeetCode 347. 前 K 个高频元素题目描述给你一个整数数组 nums 和一个整数 k请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。示例输入: nums [1,1,1,2,2,3], k 2 输出: [1,2]解法一小顶堆推荐最常用思路 先用 HashMap 统计频率然后维护一个大小为 k 的小顶堆。当堆大小超过 k 时弹出堆顶频率最小的元素最终堆中剩下的就是频率前 k 高的元素。classSolution{publicint[]topKFrequent(int[]nums,intk){// 1. 统计频率MapInteger,IntegerfreqnewHashMap();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)1);}// 2. 小顶堆按频率升序PriorityQueueint[]pqnewPriorityQueue((a,b)-a[1]-b[1]);for(Map.EntryInteger,Integerentry:freq.entrySet()){pq.offer(newint[]{entry.getKey(),entry.getValue()});if(pq.size()k){pq.poll();// 弹出频率最小的}}// 3. 收集结果int[]resnewint[k];for(intik-1;i0;i--){res[i]pq.poll()[0];}returnres;}}· 时间复杂度 O(n log k)· 空间复杂度 O(n)解法二桶排序最优O(n)思路 频率最大值不超过 n。创建 n1 个桶桶的下标为频率把相同频率的元素放进同一个桶。然后从高频桶向低频桶遍历取前 k 个元素。classSolution{publicint[]topKFrequent(int[]nums,intk){MapInteger,IntegerfreqnewHashMap();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)1);}// 桶下标为频率ListInteger[]bucketsnewList[nums.length1];for(Map.EntryInteger,Integerentry:freq.entrySet()){intfentry.getValue();if(buckets[f]null){buckets[f]newArrayList();}buckets[f].add(entry.getKey());}// 从高频到低频收集int[]resnewint[k];intidx0;for(intibuckets.length-1;i0idxk;i--){if(buckets[i]!null){for(intnum:buckets[i]){res[idx]num;if(idxk)break;}}}returnres;}}· 时间复杂度 O(n)· 空间复杂度 O(n)解法三快速选择Quickselect思路 把 (元素, 频率) 转成数组用快速选择找第 k 大的分割点平均 O(n)。classSolution{publicint[]topKFrequent(int[]nums,intk){MapInteger,IntegerfreqnewHashMap();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)1);}int[][]arrnewint[freq.size()][2];inti0;for(Map.EntryInteger,Integere:freq.entrySet()){arr[i]newint[]{e.getKey(),e.getValue()};}quickSelect(arr,0,arr.length-1,k);int[]resnewint[k];for(intj0;jk;j){res[j]arr[j][0];}returnres;}// 将前 k 大的元素无序放到数组前 k 位privatevoidquickSelect(int[][]arr,intleft,intright,intk){if(leftright)return;intpivotpartition(arr,left,right);intcountpivot-left1;// 左侧含 pivot的元素个数if(countk){return;}elseif(countk){quickSelect(arr,left,pivot-1,k);}else{quickSelect(arr,pivot1,right,k-count);}}// 按频率降序分区左侧频率 pivot 频率privateintpartition(int[][]arr,intleft,intright){int[]pivotarr[right];intileft;for(intjleft;jright;j){if(arr[j][1]pivot[1]){int[]tmparr[i];arr[i]arr[j];arr[j]tmp;i;}}int[]tmparr[i];arr[i]arr[right];arr[right]tmp;returni;}}· 时间复杂度 平均 O(n)最坏 O(n²)· 空间复杂度 O(n)对比总结解法 时间复杂度 空间复杂度 特点小顶堆 O(n log k) O(n) 最通用、面试首选k 较小时优秀桶排序 O(n) O(n) 最优时间思路直观快速选择 平均 O(n) O(n) 原地操作工程实现稍复杂面试建议 先写小顶堆版本思路清晰、不易写错再补充说明桶排序可以达到 O(n) 的优化思路。
LeetCode 347. 前 K 个高频元素题目描述给你一个整数数组 nums 和一个整数 k请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。示例输入: nums [1,1,1,2,2,3], k 2 输出: [1,2]解法一小顶堆推荐最常用思路 先用 HashMap 统计频率然后维护一个大小为 k 的小顶堆。当堆大小超过 k 时弹出堆顶频率最小的元素最终堆中剩下的就是频率前 k 高的元素。classSolution{publicint[]topKFrequent(int[]nums,intk){// 1. 统计频率MapInteger,IntegerfreqnewHashMap();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)1);}// 2. 小顶堆按频率升序PriorityQueueint[]pqnewPriorityQueue((a,b)-a[1]-b[1]);for(Map.EntryInteger,Integerentry:freq.entrySet()){pq.offer(newint[]{entry.getKey(),entry.getValue()});if(pq.size()k){pq.poll();// 弹出频率最小的}}// 3. 收集结果int[]resnewint[k];for(intik-1;i0;i--){res[i]pq.poll()[0];}returnres;}}· 时间复杂度 O(n log k)· 空间复杂度 O(n)解法二桶排序最优O(n)思路 频率最大值不超过 n。创建 n1 个桶桶的下标为频率把相同频率的元素放进同一个桶。然后从高频桶向低频桶遍历取前 k 个元素。classSolution{publicint[]topKFrequent(int[]nums,intk){MapInteger,IntegerfreqnewHashMap();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)1);}// 桶下标为频率ListInteger[]bucketsnewList[nums.length1];for(Map.EntryInteger,Integerentry:freq.entrySet()){intfentry.getValue();if(buckets[f]null){buckets[f]newArrayList();}buckets[f].add(entry.getKey());}// 从高频到低频收集int[]resnewint[k];intidx0;for(intibuckets.length-1;i0idxk;i--){if(buckets[i]!null){for(intnum:buckets[i]){res[idx]num;if(idxk)break;}}}returnres;}}· 时间复杂度 O(n)· 空间复杂度 O(n)解法三快速选择Quickselect思路 把 (元素, 频率) 转成数组用快速选择找第 k 大的分割点平均 O(n)。classSolution{publicint[]topKFrequent(int[]nums,intk){MapInteger,IntegerfreqnewHashMap();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)1);}int[][]arrnewint[freq.size()][2];inti0;for(Map.EntryInteger,Integere:freq.entrySet()){arr[i]newint[]{e.getKey(),e.getValue()};}quickSelect(arr,0,arr.length-1,k);int[]resnewint[k];for(intj0;jk;j){res[j]arr[j][0];}returnres;}// 将前 k 大的元素无序放到数组前 k 位privatevoidquickSelect(int[][]arr,intleft,intright,intk){if(leftright)return;intpivotpartition(arr,left,right);intcountpivot-left1;// 左侧含 pivot的元素个数if(countk){return;}elseif(countk){quickSelect(arr,left,pivot-1,k);}else{quickSelect(arr,pivot1,right,k-count);}}// 按频率降序分区左侧频率 pivot 频率privateintpartition(int[][]arr,intleft,intright){int[]pivotarr[right];intileft;for(intjleft;jright;j){if(arr[j][1]pivot[1]){int[]tmparr[i];arr[i]arr[j];arr[j]tmp;i;}}int[]tmparr[i];arr[i]arr[right];arr[right]tmp;returni;}}· 时间复杂度 平均 O(n)最坏 O(n²)· 空间复杂度 O(n)对比总结解法 时间复杂度 空间复杂度 特点小顶堆 O(n log k) O(n) 最通用、面试首选k 较小时优秀桶排序 O(n) O(n) 最优时间思路直观快速选择 平均 O(n) O(n) 原地操作工程实现稍复杂面试建议 先写小顶堆版本思路清晰、不易写错再补充说明桶排序可以达到 O(n) 的优化思路。
![打卡信奥刷题（3644）用C++实现信奥题 P12027 [USACO25OPEN] Ski Slope S](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3644）用C++实现信奥题 P12027 [USACO25OPEN] Ski Slope S)
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
