力扣Hot100系列16（Java）——[堆]总结()-洪萨配资

文章目录

前言
一、数组中的第K个大的元素
- 1.题目
- 2.代码
- 3. 例子
二、前k个高频元素
- 1.题目
- 2.代码
- 3.理解
- - 1.PriorityQueue的排序规则
  - 2.offer方法和add方法的区别
- 4. 例子
三、数据流中的中位数
- 1.题目
- 2.代码
- 3. 例子

前言

本文记录力扣Hot100里面关于堆的三道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

一、数组中的第K个大的元素

1.题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

2.代码

classSolution{publicintfindKthLargest(int[]nums,intk){Queue<Integer>queue=newPriorityQueue<>();// new PriorityQueue<>((a, b) -> (b - a)); 如果这样写就是大顶堆for(inti=0;i<nums.length;i++){queue.offer(nums[i]);if(queue.size()>k){queue.poll();}}returnqueue.poll();}}

Queue<Integer> queue = new PriorityQueue<>();

Java的PriorityQueue默认是小顶堆（堆顶元素是整个堆中最小的元素）

3. 例子

输入数组：nums = [3,2,1,5,6,4]
要找的目标：第2个最大的元素（预期结果是5）
核心逻辑：用小顶堆维护当前最大的k个元素，超过k个就移除堆里最小的元素，最终堆顶就是第k大元素。

初始化：创建一个空的小顶堆queue。
遍历第一个元素 3：
- 把3加入堆，堆内元素为 [3]（小顶堆堆顶是3）。
- 堆的大小是1，小于k=2，不做移除操作。
遍历第二个元素 2：
- 把2加入堆，堆会自动调整为小顶堆，堆内元素为 [2, 3]（堆顶是2）。
- 堆的大小是2，等于k=2，不做移除操作。
遍历第三个元素 1：
- 把1加入堆，堆内元素变为 [1, 3, 2]（堆顶是1）。
- 堆的大小是3，超过了k=2，需要移除堆顶（最小的元素1）。
- 移除后堆内元素回到 [2, 3]（堆顶是2）。
遍历第四个元素 5：
- 把5加入堆，堆内元素变为 [2, 3, 5]（堆顶是2）。
- 堆的大小是3，超过k=2，移除堆顶的2。
- 移除后堆内元素变为 [3, 5]（堆顶是3）。
遍历第五个元素 6：
- 把6加入堆，堆内元素变为 [3, 5, 6]（堆顶是3）。
- 堆的大小是3，超过k=2，移除堆顶的3。
- 移除后堆内元素变为 [5, 6]（堆顶是5）。
遍历第六个元素 4：
- 把4加入堆，堆会自动调整为小顶堆，堆内元素变为 [4, 6, 5]（堆顶是4）。
- 堆的大小是3，超过k=2，移除堆顶的4。
- 移除后堆内元素回到 [5, 6]（堆顶是5）。

最终结果
遍历完所有元素后，堆里只剩下数组中最大的2个元素：5和6（小顶堆的堆顶是5）。执行return queue.poll();弹出堆顶元素5，这就是数组中第2个最大的元素，和预期结果一致。

二、前k个高频元素

1.题目

给你一个整数数组 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]

2.代码

步骤：

初始化结果数组：创建长度为k的数组res，用于存储最终的前k个高频元素。
统计元素频率：
- 初始化HashMap，以数组元素为key、元素出现次数为value；
- 遍历数组，用getOrDefault方法更新每个元素的频率（不存在则默认0，存在则+1）。
初始化小顶堆：
- 创建存储Map.Entry（键值对）的优先队列，自定义比较器按value（频率）升序排序，形成小顶堆（频率最小的在堆顶）。
筛选前k个高频元素：
- 遍历HashMap的所有键值对，将每个键值对加入小顶堆；
- 若堆的大小超过k，移除堆顶元素（当前堆中频率最小的元素），确保堆中始终只保留遍历过的元素里频率最高的k个。
提取结果并返回：
- 遍历k次，依次弹出堆顶的键值对，取出其中的key（元素值）存入结果数组；
- 返回结果数组，数组内即为频率前k高的元素。

classSolution{publicint[]topKFrequent(int[]nums,intk){// 前k个高频元素,小顶堆int[]res=newint[k];// 统计每个元素的"频率"，存储到Map中，key是元素值，value是元素的"频率"Map<Integer,Integer>map=newHashMap<>();for(intnum:nums){map.put(num,map.getOrDefault(num,0)+1);}// 使用小顶堆，堆中存储的是 Map的<key,value> 键值对// 并且排序规则是以value为比较, 即以元素的"频率"大小为比较Queue<Map.Entry<Integer,Integer>>queue=newPriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue()// 注意这样写是小顶堆，反过来就是大顶堆);for(Map.Entry<Integer,Integer>entry:map.entrySet()){queue.add(entry);if(queue.size()>k){queue.poll();}}// 将堆内剩余k个元素结果放到数组中返回。剩余k个元素即"频率"最高的k个元素for(inti=0;i<k;i++){res[i]=queue.poll().getKey();// 由于堆中存的是键值对，所以这里需要getKey}returnres;}}

3.理解

1.PriorityQueue的排序规则

Queue<Map.Entry<Integer,Integer>>queue=newPriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue()// 注意这样写是小顶堆，反过来就是大顶堆);

场景1：存储基本类型（Integer、Double 等）

// 这行代码：默认小根堆Queue<Integer>queue=newPriorityQueue<>();queue.add(3);queue.add(1);queue.add(2);System.out.println(queue.peek());// 输出 1（堆顶是最小元素）

PriorityQueue 对Integer等基本类型的包装类，默认按照自然顺序升序排列，所以堆顶是最小值，也就是小根堆。
等价于手动写比较器：new PriorityQueue<>((a, b) -> a - b)（a - b 结果为正则a排在b后面，最小的在堆顶）。

场景2：存储自定义类型（如 Map.Entry）

// 自定义小根堆（按value升序）Queue<Map.Entry<Integer,Integer>>queue=newPriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue());

因为Map.Entry不是基本类型，没有默认的“自然顺序”，所以必须手动指定比较器。
这里的o1.getValue()-o2.getValue()，本质和a - b是同一个逻辑：按value升序排列，value最小的在堆顶，也就是按value排序的小根堆。

2.offer方法和add方法的区别

add()和offer()的核心功能是一样的：都是向队列（堆）中添加元素。两者的唯一区别在于添加失败时的处理方式——一个抛异常，一个返回布尔值。

1. 方法定义与失败处理（Java 官方规范）

方法	成功返回值	失败场景（队列满了）	失败处理方式
`add(E e)`	`true`	队列容量达到上限	抛出`IllegalStateException`异常
`offer(E e)`	`true`/`false`	队列容量达到上限	返回`false`（不抛异常，静默失败）

2. 结合你的使用场景（PriorityQueue）
你在找第k大元素、数据流中位数等代码中用到的PriorityQueue是无界队列（理论上没有容量上限，只要内存足够就能一直加元素），所以：

调用add()：永远返回true，永远不会触发“队列满”的失败场景，也就永远不会抛异常；
调用offer()：永远返回true，同样不会触发失败场景。

结论：在PriorityQueue中，add()和offer()完全等价，你可以随便换用，比如把代码里的queue.offer(nums[i])改成queue.add(nums[i])，运行结果不会有任何变化。

3. 什么时候能看出区别？（有界队列示例）
只有在有界队列（比如ArrayBlockingQueue，创建时指定固定容量）中，才能体现两者的差异：

// 创建一个容量为2的有界队列Queue<Integer>queue=newArrayBlockingQueue<>(2);queue.add(1);// 成功，返回truequeue.offer(2);// 成功，返回true// 尝试添加第三个元素：queue.add(3);// 失败，直接抛出 IllegalStateException 异常booleanresult=queue.offer(3);// 失败，返回false，不抛异常

总结

核心区别：添加失败时，add()抛异常，offer()返回false；
无界队列（如 PriorityQueue）中，两者完全等价；
有界队列中，offer()更适合优雅处理“队列满”的情况。

4. 例子

输入数组：nums = [1,1,1,2,2,3]
目标：找前k=2个高频元素（预期结果：1、2）

步骤1：初始化结果数组
创建长度为2的数组res，此时res = [0, 0]（初始值）。

步骤2：统计元素频率
遍历数组[1,1,1,2,2,3]，用HashMap统计每个元素的出现次数：

遍历1：map中1的频率从0→1
遍历1：map中1的频率从1→2
遍历1：map中1的频率从2→3
遍历2：map中2的频率从0→1
遍历2：map中2的频率从1→2
遍历3：map中3的频率从0→1
最终map内容：{1=3, 2=2, 3=1}（1出现3次，2出现2次，3出现1次）。

步骤3：初始化小顶堆
创建存储Map.Entry的优先队列，比较规则为“按value（频率）升序”，此时堆为空。

步骤4：筛选前k个高频元素
遍历map的3个键值对，逐个加入堆并维护堆大小不超过2：

处理键值对(1,3)：
- 加入堆，堆内元素：[(1,3)]，堆大小1（≤2），不移除元素；
处理键值对(2,2)：
- 加入堆，堆自动调整为小顶堆（按频率升序），堆内元素：[(2,2), (1,3)]（堆顶是频率2的2），堆大小2（=2），不移除元素；
处理键值对(3,1)：
- 加入堆，堆内元素：[(3,1), (1,3), (2,2)]，堆大小3（>2）；
- 移除堆顶元素（频率最小的(3,1)），堆内剩余：[(2,2), (1,3)]。

步骤5：提取结果并返回
遍历2次，弹出堆顶元素并提取key存入res：

第一次弹出堆顶(2,2)，提取key=2，res[0] = 2；
第二次弹出堆顶(1,3)，提取key=1，res[1] = 1；
最终res =[2, 1]，返回该数组（顺序不影响，只要是前2个高频元素即可）。

三、数据流中的中位数

1.题目

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10(-5) 以内的答案将被接受。

示例 1：
输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]

输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

2.代码

1. 初始化（构造方法）

定义两个优先队列：queMin为大顶堆（存储较小一半元素，堆顶是该部分最大值），queMax为小顶堆（存储较大一半元素，堆顶是该部分最小值）。

2. 添加元素（addNum 方法）

判定归属：若数字≤queMin堆顶（或queMin为空），放入queMin；否则放入queMax。
平衡堆大小：
- 若queMin比queMax多超过1个，将queMin堆顶移到queMax；
- 若queMax大小超过queMin，将queMax堆顶移到queMin；
- 最终保证queMin大小 =queMax大小或queMin大小 =queMax大小+1。

3. 查找中位数（findMedian 方法）

若元素总数为奇数（queMin更大），中位数是queMin堆顶；
若元素总数为偶数（两堆大小相等），中位数是两堆顶数值的平均值。

classMedianFinder{// 大顶堆：存储较小的一半元素，堆顶是这部分的最大值PriorityQueue<Integer>queMin;// 小顶堆：存储较大的一半元素，堆顶是这部分的最小值PriorityQueue<Integer>queMax;// 初始化堆：queMin大顶堆，queMax小顶堆publicMedianFinder(){queMin=newPriorityQueue<Integer>((a,b)->(b-a));queMax=newPriorityQueue<Integer>((a,b)->(a-b));}// 添加元素，维持堆平衡：queMin.size() = queMax.size() 或 queMin.size() = queMax.size()+1publicvoidaddNum(intnum){// 元素归入较小半区（queMin）if(queMin.isEmpty()||num<=queMin.peek()){queMin.offer(num);// 平衡：queMin超出queMax+1时，移堆顶到queMaxif(queMax.size()+1<queMin.size()){queMax.offer(queMin.poll());}}else{// 元素归入较大半区（queMax）queMax.offer(num);// 平衡：queMax超过queMin时，移堆顶到queMinif(queMax.size()>queMin.size()){queMin.offer(queMax.poll());}}}// 获取中位数：奇数取queMin堆顶，偶数取两堆顶平均值publicdoublefindMedian(){if(queMin.size()>queMax.size()){returnqueMin.peek();}return(queMin.peek()+queMax.peek())/2.0;}}

3. 例子

以5 → 2 → 7 → 1 → 9为例：

数据流添加顺序：5 → 2 → 7 → 1 → 9
规则：queMin（大顶堆，存较小半区）、queMax（小顶堆，存较大半区）
保证queMin.size()=queMax.size()或queMin.size()=queMax.size()+1

初始化
queMin（大顶堆）为空，queMax（小顶堆）为空。

步骤1：添加元素 5

判定归属：queMin为空，将5放入queMin；
平衡堆大小：queMin.size()=1，queMax.size()=0（符合规则），无需调整；
当前堆状态：queMin=[5]（堆顶5）、queMax=[]；
查中位数：总数奇数，中位数=5。

步骤2：添加元素 2

判定归属：2 ≤queMin堆顶5，放入queMin；
平衡堆大小：queMin.size()=2，queMax.size()=0（queMin比queMax多2个，超出规则），将queMin堆顶5移到queMax；
当前堆状态：queMin=[2]（堆顶2）、queMax=[5]（堆顶5）；
查中位数：总数偶数，中位数=(2+5)/2=3.5。

步骤3：添加元素 7

判定归属：7 >queMin堆顶2，放入queMax；
平衡堆大小：queMax.size()=2>queMin.size()=1，将queMax堆顶5移到queMin；
当前堆状态：queMin=[5,2]（大顶堆，堆顶5）、queMax=[7]（堆顶7）；
查中位数：总数奇数，中位数=5。

步骤4：添加元素 1

判定归属：1 ≤queMin堆顶5，放入queMin；
平衡堆大小：queMin.size()=3，queMax.size()=1（queMin比queMax多2个），将queMin堆顶5移到queMax；
当前堆状态：queMin=[2,1]（堆顶2）、queMax=[5,7]（堆顶5）；
查中位数：总数偶数，中位数=(2+5)/2=3.5。