目录
1. 最后一块石头的重量
1.1 算法原理
- 建一个大根堆, 每次取出的元素就是最大值, 每次连取两个元素, 进行抵消, 再将差值放入堆中.
- 当堆中的元素 <= 1 时, 就是最后一块石头的重量.
1.2 算法代码
class Solution {
public int lastStoneWeight(int[] stones) {
// 建大根堆
PriorityQueue<Integer> heap = new PriorityQueue<>((n1, n2) -> n2 - n1);
for(int x : stones) heap.offer(x);
while(heap.size() > 1) {
int x = heap.poll();
int y = heap.poll();
if(x != y) heap.offer(x - y);
}
return heap.isEmpty() ? 0 : heap.poll();
}
}2. 数据流中的第 K 大元素
2.1 算法原理
Top-K 问题
1. 求第 k 个最大值 => 建小堆
- 理解1: 堆顶元素最小, 若有元素大于堆顶元素, 则poll出堆顶元素, 将新元素入堆. 全部元素比较完后, 堆中的元素就是最大的几个值.
- 理解2: (反向假设) 若建大堆, 堆顶元素是最大的, 但是堆中可能存在更小的值, 而我们无法与堆内部的元素进行比较
2. 求第 k 个最小值 => 建大堆
- 理解1: 堆顶元素最大, 若有元素小于堆顶元素, 则poll出堆顶元素, 将新元素入堆. 全部元素比较完后, 堆中的元素就是最小的几个值.
- 理解2: (反向假设) 若建小堆, 堆顶元素是最小的, 但是堆中可能存在更大的值, 而我们无法与堆内部的元素进行比较
2.2 算法代码
class KthLargest {
PriorityQueue<Integer> queue;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
queue = new PriorityQueue<>();
for(int x : nums) {
queue.offer(x);
if(queue.size() > k) queue.poll();
}
}
public int add(int val) {
queue.offer(val);
if(queue.size() > k) queue.poll();
return queue.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/3. 前 K 个高频单词
3.1 算法原理
- Top-K 问题
1. 使用哈希表, 统计每个单词出现的频率 Map<String, Integer>
2. 建堆 Pair<String, Integer>
2.1 如果两个单词出现的频率不相同 => 根据单词的出现频率, 建小堆
2.2 如果两个单词出现的频率相同 => 根据字典序, 建大堆
3. 循环将元素入堆, 当堆中元素大于 k 时, 将堆顶元素出堆
4. 最终, 堆中的元素就是频次出现最高的 k 个元素, 放入数组中
5. 数组逆序
3.2 算法代码
class Solution {
public List<String> topKFrequent(String[] words, int k) {
// 统计每个字符串出现的频次
Map<String, Integer> hash = new HashMap<>();
for(String str : words) {
if(!hash.containsKey(str)) hash.put(str, 1);
else hash.put(str, hash.get(str) + 1);
}
// 预处理堆
PriorityQueue<Pair<String ,Integer>> heap = new PriorityQueue<>((p1, p2) -> {
int n1 = p1.getValue(), n2 = p2.getValue();
if(n1 != n2) return n1 - n2;
else return p2.getKey().compareTo(p1.getKey());
});
// Top-K
for(Map.Entry<String, Integer> e : hash.entrySet()) {
heap.offer(new Pair<>(e.getKey(), e.getValue()));
if(heap.size() > k) {
heap.poll();
}
}
List<String> ret = new ArrayList<>();
while(!heap.isEmpty()) ret.add(heap.poll().getKey());
Collections.reverse(ret);
return ret;
}
}4. 数据流的中位数
4.1 算法原理
- 解法一: 每插入一个元素, 进行一次排序 => O(N*logN) 超时
- 解法二: 没插入一个元素, 进行一次插入排序 => O(N) 超时
- 解法三: 利用大小堆, 获取中位数
大堆放入有序序列的前 m 个元素, 小堆放入有序序列的后 n 个元素 (要求: m == n || m == n + 1)
此时, 大小堆的堆顶元素就是有序序列中间位置的两个元素
注意 add 时, 要添加的数据和左堆/右堆数量不匹配的问题
4.2 算法代码
class MedianFinder {
PriorityQueue<Integer> left;
PriorityQueue<Integer> right;
public MedianFinder() {
// 大堆
left = new PriorityQueue<>((a, b) -> b - a);
// 小堆
right = new PriorityQueue<>();
}
public void addNum(int num) {
int m = left.size(), n = right.size();
if(m == n) {
if(left.isEmpty() || left.peek() >= num) left.offer(num);
else {
right.offer(num);
left.offer(right.poll());
}
}
if(m == n + 1) {
if(left.peek() >= num) {
left.offer(num);
right.offer(left.poll());
}else right.offer(num);
}
}
public double findMedian() {
int m = left.size(), n = right.size();
if(m == n + 1) return left.peek();
else return (left.peek() + right.peek()) / 2.0;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/END
标签：优先级,队列,元素,int,算法,heap,poll,left From： https://blog.csdn.net/2401_83595513/article/details/143509530