本文概览本文讲解前 K 个高频元素的核心思路先用哈希表统计频率再用按频率比较的大小为 k 的最小堆求前 k 个框架复用上一题只换比较器一、题目二、题目分析1. 题目要求给定一个整数数组nums和一个整数k返回其中出现频率前k高的元素。例子nums [1, 1, 1, 2, 2, 3]k 2元素: 1 2 3 频率: 3 2 1 前 2 个高频元素 → [1, 2]和上一题的区别上一题比的是元素值的大小这题比的是出现频率的高低。元素本身多大无所谓谁出现得多谁排前面。2. 第一步先统计频率两种思路共同的前置步骤要比频率先得知道每个元素的频率。原始数组是乱的直接看不出来所以第一步都是一样的用哈希表统计每个元素的出现次数。nums [1, 1, 1, 2, 2, 3] 遍历统计 1 → 出现 3 次 2 → 出现 2 次 3 → 出现 1 次 map {1: 3, 2: 2, 3: 1}统计完之后问题就变成了在 (元素, 频率) 条目里找频率最高的前 k 个——这不就是上一题的 Top K 问题吗3. 方法一按频率整体排序最直觉的做法把所有条目按频率降序排序取前 k 个。排序可以直接用List.sort内部就是归并一类的稳定排序不需要手写归并或快排。问题和上一题一样整体排序是 O(m log m)m 为不同元素的个数但我们只需要前 k 个排后面的部分完全浪费了。4. 方法二大小为 k 的最小堆框架和上一题完全一致依旧是维护一个大小为 k 的最小堆堆里始终保留目前见过的频率前 k 高的元素堆顶就是门槛。唯一要改的地方堆的比较规则。上一题堆里存的是整数默认按数值比这题要按频率比——也就是说需要重写这个最小堆的排序器可以用 lambda 简写PriorityQueueIntegerminHeapnewPriorityQueue(Comparator.comparingInt(map::get));最小堆的原理物理数组 逻辑完全二叉树、上浮、下沉在上一篇博客里已经详细讲解过这里不再重复不熟悉的可以先看数组中的第K个最大元素CSDN数组中的第K个最大元素个人博客三、思路概览方法一排序publicint[]topKFrequent(int[]nums,intk){// 哈希表统计元素出现次数MapInteger,IntegermapnewHashMap();for(intnum:nums){map.put(num,map.getOrDefault(num,0)1);}// 所有条目按频率降序排序ListMap.EntryInteger,IntegerlistnewArrayList(map.entrySet());list.sort((a,b)-b.getValue()-a.getValue());// 取前 k 个int[]resnewint[k];for(inti0;ik;i){res[i]list.get(i).getKey();}returnres;}时间复杂度 O(m log m)m 为不同元素个数。方法二大小为 k 的最小堆publicint[]topKFrequent(int[]nums,intk){// 哈希表统计元素出现次数MapInteger,IntegermapnewHashMap();for(intnum:nums){map.put(num,map.getOrDefault(num,0)1);}// 堆排序按频率比较的最小堆PriorityQueueIntegerminHeapnewPriorityQueue(Comparator.comparingInt(map::get));for(Map.EntryInteger,Integerentry:map.entrySet()){// 堆没满 k 个直接入堆if(minHeap.size()k){minHeap.offer(entry.getKey());}else{// 新条目的频率 堆顶元素的频率替换if(entry.getValue()map.get(minHeap.peek())){minHeap.poll();minHeap.offer(entry.getKey());}}}// 从堆中获取前 k 个元素int[]resnewint[k];for(intik-1;i0;i--){res[i]minHeap.poll();}returnres;}思路简要说明前置统计HashMap 记录每个元素的出现次数比较规则换成频率Comparator.comparingInt(map::get)堆内存元素值但比较时通过 map 查频率框架与上一题一致堆没满直接入满了之后新条目频率 堆顶频率才替换结果倒着填poll 吐出的是按频率从小到大的顺序从数组末位往前填结果就是频率从高到低时间复杂度 O(m log k)m 个条目每个最多一次入堆/出堆单次 O(log k)四、思路详解第一步为什么第一步必须是哈希表统计频率信息在原始数组里是隐藏的。要比较两个元素谁的频率高就得知道它们各出现了多少次要知道出现了多少次就得扫一遍数组数一数。所以不管后面用排序还是用堆第一步都是把频率数出来存进哈希表元素 → 频率。这一步顺便完成了去重——数组里的重复元素在 map 里只剩一个条目后面处理的就是 m 个不同元素的条目而不是 n 个原始元素。第二步这题和上一题到底哪里一样、哪里不一样一样的框架直接复用都是 Top K 问题留前 k 个、踢掉其余都是大小为 k 的最小堆堆顶是门槛替换逻辑一样新条目 堆顶门槛 → 弹出堆顶、加入新条目不一样的比较规则上一题比较的是元素值堆内存的 Integer 本身就能比这题比较的是频率堆里存的元素值比如 1 和 2本身比大小没有意义1 比 2 小但 1 的频率比 2 高要留下的是 1所以关键动作就是重写比较器把比数值换成比 map 里查出来的频率。第三步Comparator.comparingInt(map::get)是怎么工作的PriorityQueue构造时可以传入一个比较器堆内部所有比较上浮、下沉时的父子比较都会用它。拆开看这段代码Comparator.comparingInt(map::get)map::get方法引用等价于元素 - map.get(元素)即传入堆里的元素查出它的频率Comparator.comparingInt(...)拿查出来的频率做 int 比较效果堆里存的还是元素值Integer但每次需要比较两个元素谁更小时实际比的是它们的频率。频率小的在堆顶。这样一来上一题讲的上浮、下沉、索引公式全部原样生效只是大小的定义换了。第四步替换条件的细节if(entry.getValue()map.get(minHeap.peek())){minHeap.poll();minHeap.offer(entry.getKey());}两个容易看错的地方左边是entry.getValue()当前遍历条目的频率右边是map.get(minHeap.peek())先peek()拿到堆顶的元素值再拿这个元素值去 map 查频率两边比的都是频率不是元素值。这个写法比上一题多绕了一层堆里是元素、比的是频率读代码时要注意区分。第五步结果数组为什么倒着填int[]resnewint[k];for(intik-1;i0;i--){res[i]minHeap.poll();}poll 依次吐出的是按频率从小到大的顺序每次吐当前最小poll 顺序频率从小到大: 第1个 第2个 ... 第k个 填入位置: res[k-1] res[k-2] ... res[0]从res[k-1]往res[0]倒着填res[0]最后填的是频率最高的最终结果就是频率从高到低的顺序。题目其实不要求结果有序但这样写顺便得到了有序结果而且循环结构很自然。完整执行过程以nums [1, 1, 1, 2, 2, 3]k 2为例第一步统计频率元素: 1 2 3 频率: 3 2 1 map {1: 3, 2: 2, 3: 1}第二步遍历条目维护堆堆内括号标注频率entry 1频率3size(0) 2直接入堆 minHeap [1(3)] entry 2频率2size(1) 2直接入堆 [1(3), 2(2)] → 按频率比2 3 → 2 上浮到堆顶 minHeap [2(2), 1(3)] 2(2) / 1(3) entry 3频率1size(2) 已满 频率1 堆顶 2 的频率2 1 2 不成立 → 丢弃 **第三步倒序填结果** res[1] poll() 2频率小先出 res[0] poll() 1频率大后出 res [1, 2] ✓注意 entry 3 这一步如果按元素值比3 2 会替换进去答案就错了按频率比1 2 直接丢弃——这就是比较器改对了的价值。复杂度分析时间复杂度 O(n m log k)统计频率O(n)遍历数组一次维护堆m 个条目每个最多一次入堆 一次出堆单次 O(log k)共 O(m log k)m ≤ n当 k 远小于 m 时比方法一的 O(m log m) 快空间复杂度 O(m k)哈希表存 m 个条目堆最多 k 个元素。五、总结前 K 个高频元素的核心思路前置统计HashMap 数出每个元素的频率同时完成去重框架复用和第 K 大元素完全一样的大小为 k 的最小堆框架关键改动比较器从比数值换成比频率——Comparator.comparingInt(map::get)替换条件两边都是频率entry.getValue()vsmap.get(peek())别看错成元素值结果倒填poll 吐出频率从小到大倒着填进数组得到频率从高到低Top K 框架的复用心法容器大小永远是 k堆顶永远是门槛要留什么就定义好谁大谁小——比数值、比频率、比长度换个比较器框架原样跑这题也说明了比较器是最小堆的灵魂堆只认比较器定义的大小不管你存的是数字、元素还是对象。