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. 统计频率Map<Integer,Integer>freq=newHashMap<>();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)+1);}// 2. 小顶堆，按频率升序PriorityQueue<int[]>pq=newPriorityQueue<>((a,b)->a[1]-b[1]);for(Map.Entry<Integer,Integer>entry:freq.entrySet()){pq.offer(newint[]{entry.getKey(),entry.getValue()});if(pq.size()>k){pq.poll();// 弹出频率最小的}}// 3. 收集结果int[]res=newint[k];for(inti=k-1;i>=0;i--){res[i]=pq.poll()[0];}returnres;}}

· 时间复杂度： O(n log k)
· 空间复杂度： O(n)

解法二：桶排序（最优，O(n)）

思路： 频率最大值不超过 n。创建 n+1 个桶，桶的下标为频率，把相同频率的元素放进同一个桶。然后从高频桶向低频桶遍历，取前 k 个元素。

classSolution{publicint[]topKFrequent(int[]nums,intk){Map<Integer,Integer>freq=newHashMap<>();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)+1);}// 桶：下标为频率List<Integer>[]buckets=newList[nums.length+1];for(Map.Entry<Integer,Integer>entry:freq.entrySet()){intf=entry.getValue();if(buckets[f]==null){buckets[f]=newArrayList<>();}buckets[f].add(entry.getKey());}// 从高频到低频收集int[]res=newint[k];intidx=0;for(inti=buckets.length-1;i>=0&&idx<k;i--){if(buckets[i]!=null){for(intnum:buckets[i]){res[idx++]=num;if(idx==k)break;}}}returnres;}}

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

解法三：快速选择（Quickselect）

思路： 把 (元素, 频率) 转成数组，用快速选择找第 k 大的分割点，平均 O(n)。

classSolution{publicint[]topKFrequent(int[]nums,intk){Map<Integer,Integer>freq=newHashMap<>();for(intnum:nums){freq.put(num,freq.getOrDefault(num,0)+1);}int[][]arr=newint[freq.size()][2];inti=0;for(Map.Entry<Integer,Integer>e:freq.entrySet()){arr[i++]=newint[]{e.getKey(),e.getValue()};}quickSelect(arr,0,arr.length-1,k);int[]res=newint[k];for(intj=0;j<k;j++){res[j]=arr[j][0];}returnres;}// 将前 k 大的元素（无序）放到数组前 k 位privatevoidquickSelect(int[][]arr,intleft,intright,intk){if(left>=right)return;intpivot=partition(arr,left,right);intcount=pivot-left+1;// 左侧（含 pivot）的元素个数if(count==k){return;}elseif(count>k){quickSelect(arr,left,pivot-1,k);}else{quickSelect(arr,pivot+1,right,k-count);}}// 按频率降序分区：左侧频率 >= pivot 频率privateintpartition(int[][]arr,intleft,intright){int[]pivot=arr[right];inti=left;for(intj=left;j<right;j++){if(arr[j][1]>=pivot[1]){int[]tmp=arr[i];arr[i]=arr[j];arr[j]=tmp;i++;}}int[]tmp=arr[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) 的优化思路。