当前位置：首页 > news >正文

Hot100 堆

news 来源：原创 2025/9/22 12:32:26

215. 数组中的第K个最大元素 - 力扣（LeetCode）

堆排序
我们可以借助一个小顶堆来维护当前堆内元素的最小值，同时保证堆的大小为 k：

遍历数组将元素入堆；
如果当前堆内元素超过 k 了，我们就把堆顶元素去除，即去除当前的最小值。
因此我们在元素入堆的过程中，不断淘汰最小值，最终留在堆中就是数组中前 k 个最大元素，并且堆顶元素为前 k 大元素中的最小值，即为第 k 个元素。

class Solution {//我们可以借助一个小顶堆来维护当前堆内元素的最小值，同时保证堆的大小为 k：//遍历数组将元素入堆；//如果当前堆内元素超过 k 了，我们就把堆顶元素去除，即去除当前的最小值。//因此我们在元素入堆的过程中，不断淘汰最小值，最终留在堆中就是数组中前 k 个最大元素，并且堆顶元素为前 k 大元素中的最小值，即为第 k 个元素。public int findKthLargest(int[] nums, int k) {Queue<Integer> pq=new PriorityQueue<>();for(int num: nums){pq.offer(num);if(pq.size() > k){pq.poll();   // 堆中元素超过k个，弹出最小的那个}}return pq.peek();}
}

注意：这种方法并不是设置堆的大小只能是k，而是当堆为k+1大小时候自动的去删除最小的。省去了人为判断

347. 前 K 个高频元素 - 力扣（LeetCode）

这道题和上一道的区别在于我们重写了Comparator，采用了根据map.value来排序

注意：最后要通过res.stream().mapToInt(Integer::intValue).toArray()；转换回int[]

创建流：res.stream() 将 List<Integer> 转换为一个流。
映射为原始类型：mapToInt(Integer::intValue) 将流中的每个 Integer 对象转换为 int。
收集为数组：toArray() 将流中的 int 类型元素收集到一个 int[] 数组中。

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> hashmap=new HashMap<>();//借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率for(int n:nums){hashmap.put(n,hashmap.getOrDefault(n,0)+1);}//这里需要自己重写Comparater频率第k大 还是用最小堆，规则是按map的value排序PriorityQueue<Integer> pq=new PriorityQueue<>(new Comparator<Integer>(){@Overridepublic int compare(Integer a,Integer b){return hashmap.get(a)-hashmap.get(b);}});for (Integer key : hashmap.keySet()) {pq.offer(key);if(pq.size()>k) pq.poll();//去掉出现频率最小的}// 取出最小堆中的元素List<Integer> res = new ArrayList<>();while (!pq.isEmpty()) {res.add(pq.poll());}return res.stream().mapToInt(Integer::intValue).toArray();}}

在 Java 中，两个冒号 :: 是 方法引用 的语法符号，它用于直接引用已存在的方法，而无需通过匿名类或 Lambda 表达式显式调用。方法引用是 Java 8 引入的一个特性，主要用于简化代码，使其更加简洁和易读。

方法引用的作用

方法引用允许你直接引用一个类或对象的现有方法，而不是通过 Lambda 表达式重新实现相同的功能。它通常用于与函数式接口（如 Function、Consumer、Supplier 等）一起使用。

方法引用的常见形式

方法引用有以下几种形式：

静态方法引用
格式：类名::静态方法名
示例：Math::abs，表示引用 Math 类中的 abs 静态方法。
实例方法引用
格式：对象名::实例方法名
示例：string::length，表示引用某个字符串对象的 length() 方法。
类方法引用
格式：类名::实例方法名
示例：String::length，表示引用任意字符串对象的 length() 方法。
构造方法引用
格式：类名::new
示例：ArrayList::new，表示引用 ArrayList 的构造方法。

295. 数据流的中位数 - 力扣（LeetCode）

具体的，我们可以使用两个优先队列（堆）来维护整个数据流数据，令维护数据流左半边数据的优先队列（堆）为 l，维护数据流右半边数据的优先队列（堆）为 r。

显然，为了可以在 O(1) 的复杂度内取得当前中位数，我们应当令 l 为大根堆，r 为小根堆，并人为固定 l 和 r 之前存在如下的大小关系：

当数据流元素数量为偶数：l 和 r 大小相同，此时动态中位数为两者堆顶元素的平均值；
当数据流元素数量为奇数：l 比 r 多一，此时动态中位数为 l 的堆顶原数。

为了满足上述说的奇偶性堆大小关系，在进行 addNum 时，我们应当分情况处理：

1.插入前两者大小相同，总数为偶数时，即将变成奇数。先将数字放入r，然后把r中最小的数给l。将判断的权力交给堆。

2.插入前两者大小不同，总数为奇数时，即将变成偶数。先放到大根堆，然后从大根堆中拿出一个最大的放到r去

总而言之，必须保持大小 l==r 或是 l=r+1;

class MedianFinder {PriorityQueue<Integer> l = new PriorityQueue<>((a, b) -> b - a); // 大根堆PriorityQueue<Integer> r = new PriorityQueue<>((a, b) -> a - b); // 小根堆public MedianFinder() {}//永远保持l比r多1public void addNum(int num) {// 总数为偶数时，即将变成奇数。先将数字放入r，然后把r中最小的数给l。将判断的权力交给堆。if (l.size() == r.size()) {r.offer(num);l.offer(r.poll());} else { // 总数为奇数时，即将变成偶数 从大根堆中拿出一个放到r去l.offer(num);r.offer(l.poll());}}public double findMedian() {// 总数为偶数时，中位数是两个堆顶的平均值if (l.size() == r.size()) {return (l.peek() + r.peek()) / 2.0;} else { // 总数为奇数时，中位数是大根堆的堆顶return l.peek();}}
}

347. 前 K 个高频元素 - 力扣（LeetCode）

方法引用的作用

方法引用的常见形式

295. 数据流的中位数 - 力扣（LeetCode）

相关文章：