堆 / 优先队列专题二刷笔记：前 K 个高频元素 数据流的中位数

目录一、LeetCode 347. 前 K 个高频元素中等题目描述核心思路方法 1小顶堆推荐时间复杂度 O (n log k)方法 2大顶堆写法简单但效率略低代码实现Java 小顶堆版二刷复盘要点二、LeetCode 295. 数据流的中位数困难题目描述核心思路双堆法经典模板代码实现Java二刷复盘要点三、两道题的核心模板总结这两道题是堆优先队列的「面试双杀」也是我自己二刷时的重点复盘题帮你把核心模板和易错点一次性吃透。一、LeetCode 347. 前 K 个高频元素中等题目描述给你一个整数数组nums和一个整数k请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。核心思路这道题的核心是 **「统计频率 用堆筛选前 K 大」**二刷时一定要掌握两种写法的区别方法 1小顶堆推荐时间复杂度 O (n log k)统计频率用 HashMap 统计每个数字出现的次数。维护小顶堆堆的大小始终不超过k。遍历所有频率当堆大小小于k时直接入堆当堆大小等于k时如果当前频率大于堆顶元素则弹出堆顶、压入当前元素。结果收集遍历结束后堆中剩下的k个元素就是频率最高的前k个。方法 2大顶堆写法简单但效率略低直接把所有元素按频率压入大顶堆然后弹出前k个即可。但时间复杂度为 O (n log n)在数据量大时效率不如小顶堆。代码实现Java 小顶堆版java运行public int[] topKFrequent(int[] nums, int k) { // 1. 统计频率 MapInteger, Integer freqMap new HashMap(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) 1); } // 2. 小顶堆按频率升序排列堆顶是当前频率最小的元素 PriorityQueueMap.EntryInteger, Integer minHeap new PriorityQueue(Comparator.comparingInt(Map.Entry::getValue)); for (Map.EntryInteger, Integer entry : freqMap.entrySet()) { if (minHeap.size() k) { minHeap.offer(entry); } else { if (entry.getValue() minHeap.peek().getValue()) { minHeap.poll(); minHeap.offer(entry); } } } // 3. 收集结果 int[] res new int[k]; int idx 0; while (!minHeap.isEmpty()) { res[idx] minHeap.poll().getKey(); } return res; }二刷复盘要点为什么用小顶堆而不是大顶堆因为小顶堆的大小始终是k堆操作的时间复杂度是 O (log k)整体效率更高。易错点堆的比较器要写对小顶堆是按频率升序而不是按元素本身的值排序。二、LeetCode 295. 数据流的中位数困难题目描述中位数是有序列表中间的数。如果列表长度是偶数中位数是中间两个数的平均值。设计一个支持addNum和findMedian操作的数据结构addNum(int num)从数据流中添加一个整数到数据结构中。findMedian()返回目前所有元素的中位数。核心思路双堆法经典模板用两个堆分别维护数据的左右两半大顶堆left存储前半部分数据堆顶是前半部分的最大值。小顶堆right存储后半部分数据堆顶是后半部分的最小值。维护规则大顶堆的大小要么和小顶堆相等要么比小顶堆多 1保证奇数长度时大顶堆的堆顶就是中位数。每次添加元素时先根据元素大小判断该加入哪个堆再调整两个堆的大小保持平衡。代码实现Javajava运行class MedianFinder { // 大顶堆存储前半部分堆顶是前半部分的最大值 private PriorityQueueInteger left; // 小顶堆存储后半部分堆顶是后半部分的最小值 private PriorityQueueInteger right; public MedianFinder() { left new PriorityQueue((a, b) - b - a); right new PriorityQueue(); } public void addNum(int num) { // 先决定加入哪个堆 if (left.isEmpty() || num left.peek()) { left.offer(num); } else { right.offer(num); } // 调整堆的大小保持平衡 // 情况1大顶堆比小顶堆多2个需要把大顶堆的堆顶移到小顶堆 if (left.size() right.size() 1) { right.offer(left.poll()); } // 情况2小顶堆比大顶堆多需要把小顶堆的堆顶移到大顶堆 else if (right.size() left.size()) { left.offer(right.poll()); } } public double findMedian() { // 奇数个元素大顶堆的堆顶就是中位数 if (left.size() right.size()) { return left.peek(); } // 偶数个元素取两个堆顶的平均值 else { return (left.peek() right.peek()) / 2.0; } } }二刷复盘要点两个堆的作用是什么大顶堆维护左半部分小顶堆维护右半部分这样两个堆顶就是整个数据的中间两个数取中位数的时间复杂度是 O (1)。易错点堆的大小调整逻辑一定要写对尤其是大顶堆和小顶堆的大小关系否则会导致中位数计算错误。面试常问除了双堆法还有没有其他方法如二分查找维护有序数组但插入时间复杂度是 O (n)效率不如双堆法三、两道题的核心模板总结表格题目核心数据结构关键技巧时间复杂度前 K 个高频元素HashMap 小顶堆维护堆大小不超过 k效率最优O(n log k)数据流的中位数大顶堆 小顶堆双堆平衡堆顶直接取中位数addNum: O(log n), findMedian: O(1)