力扣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.代码

class Solution {
public int findKthLargest(int[] nums, int k) {

Queue<Integer> queue = new PriorityQueue<>();
// new PriorityQueue<>((a, b) -> (b – a)); 如果这样写就是大顶堆

for (int i = 0; i < nums.length; i++) {
queue.offer(nums[i]);
if(queue.size() > k){
queue.poll();
}
}

return queue.poll();
}
}

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

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

3. 例子

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

最终结果 遍历完所有元素后，堆里只剩下数组中最大的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.代码

步骤：

class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 前k个高频元素,小顶堆
int[] res = new int[k];

// 统计每个元素的"频率"，存储到Map中，key是元素值，value是元素的"频率"
Map<Integer,Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num, 0) + 1);
}

// 使用小顶堆，堆中存储的是 Map的<key,value> 键值对
// 并且排序规则是以value为比较, 即以元素的"频率"大小为比较
Queue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>(
(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(int i = 0; i < k; i++){
res[i] = queue.poll().getKey(); // 由于堆中存的是键值对，所以这里需要getKey
}
return res;
}
}

3.理解

1.PriorityQueue的排序规则

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

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

// 这行代码：默认小根堆
Queue<Integer> queue = new PriorityQueue<>();
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 = new PriorityQueue<>(
(o1,o2)-> o1.getValue()–o2.getValue()
);

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

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

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

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

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 = new ArrayBlockingQueue<>(2);
queue.add(1); // 成功，返回true
queue.offer(2); // 成功，返回true

// 尝试添加第三个元素：
queue.add(3); // 失败，直接抛出 IllegalStateException 异常
boolean result = queue.offer(3); // 失败，返回false，不抛异常

总结

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：

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

三、数据流中的中位数

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堆顶；
• 若元素总数为偶数（两堆大小相等），中位数是两堆顶数值的平均值。

class MedianFinder {
// 大顶堆：存储较小的一半元素，堆顶是这部分的最大值
PriorityQueue<Integer> queMin;
// 小顶堆：存储较大的一半元素，堆顶是这部分的最小值
PriorityQueue<Integer> queMax;

// 初始化堆：queMin大顶堆，queMax小顶堆
public MedianFinder() {
queMin = new PriorityQueue<Integer>((a, b) -> (b – a));
queMax = new PriorityQueue<Integer>((a, b) -> (a – b));
}

// 添加元素，维持堆平衡：queMin.size() = queMax.size() 或 queMin.size() = queMax.size()+1
public void addNum(int num) {
// 元素归入较小半区（queMin）
if (queMin.isEmpty() || num <= queMin.peek()) {
queMin.offer(num);
// 平衡：queMin超出queMax+1时，移堆顶到queMax
if (queMax.size() + 1 < queMin.size()) {
queMax.offer(queMin.poll());
}
} else {
// 元素归入较大半区（queMax）
queMax.offer(num);
// 平衡：queMax超过queMin时，移堆顶到queMin
if (queMax.size() > queMin.size()) {
queMin.offer(queMax.poll());
}
}
}

// 获取中位数：奇数取queMin堆顶，偶数取两堆顶平均值
public double findMedian() {
if (queMin.size() > queMax.size()) {
return queMin.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

步骤2：添加元素 2

步骤3：添加元素 7

步骤4：添加元素 1

步骤5：添加元素 9

如果本篇文章对您有帮助，可以点赞，收藏或评论哦！！！关注主包不迷路，让我们一起向前进步吧！！