文章标题：
优先队列在算法问题中的巧妙应用
目录
- 一、1046.最后的石头重量计算
- 二、703. 数据流里的第 K 大元素
- 三、692. 前 K 个高频词语
- 四、295. 数据流的中位数求解
一、1046.最后的石头重量计算
题目链接：1046.最后的石头重量
题目描述：
题目解析：
- 该问题要求我们从给定的数组中不断取出最大的两个元素，让它们相减后将差值重新放入数组，重复此过程直到数组为空或只剩一个元素。
解题思路：
- 直接对数组排序会频繁操作，效率不高。此时可使用优先队列（大根堆），能快速取出最大元素，降低操作开销。
解题代码：
//时间复杂度 O(n)
//空间复杂度 O(n)
class Solution {
public int lastStoneWeight(int[] stones) {
//创建大根堆
PriorityQueue<Integer> queue = new PriorityQueue<>(
(a,b) -> b - a
);
//将数组元素加入堆中
for(int i = 0; i < stones.length; i++)
queue.offer(stones[i]);
//循环处理，直到堆中只剩一个或没有元素
while(!queue.isEmpty() && queue.size() != 1) {
int y = queue.poll();
int x = queue.poll();
queue.offer(y-x);
}
//返回结果，如果堆为空返回0，否则返回剩余元素
return queue.isEmpty() ? 0 : queue.poll();
}
}
二、703. 数据流里的第 K 大元素
题目链接：703. 数据流中的第 K 大元素
题目描述：
题目解析：
- 给定一个数组和整数K，需通过类的add方法，每次添加元素后返回当前数组中第K大的元素。
解题思路：
- 利用大小为K的小根堆，堆中始终保存当前数组中第K大到最大的元素，堆顶即为第K大元素。
解题代码：
//时间复杂度 O(nLogK)
//空间复杂度 O(K)
class KthLargest {
PriorityQueue<Integer> heap;
int kValue;
public KthLargest(int k, int[] nums) {
heap = new PriorityQueue<Integer>();
kValue = k;
for(int i = 0; i < nums.length; i++) {
heap.offer(nums[i]);
if(heap.size() > kValue) {
heap.poll();
}
}
}
public int add(int val) {
heap.offer(val);
if(heap.size() > kValue) {
heap.poll();
}
return heap.peek();
}
}
三、692. 前 K 个高频词语
题目链接：692. 前 K 个⾼频单词
题目描述：
题目解析：
- 给定字符串数组words，需找出出现频率最高的前K个字符串，频率相同时按字典序从小到大排列。
解题思路：
- 先用哈希表统计字符串出现次数，再用大小为K的堆，结合自定义比较器处理频率和字典序，最后逆序结果得到正确顺序。
解题代码：
//时间复杂度：O(NLogK)
//空间复杂度：O(N)
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> countMap = new HashMap<>();
PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
(a,b) -> {
//频率相同时按字典序降序，保证弹出时为升序
if(a.getValue().equals(b.getValue())) {
return b.getKey().compareTo(a.getKey());
}
//频率不同时按升序
return a.getValue() - b.getValue();
});
//统计单词出现次数
for( String s : words) {
countMap.put(s, countMap.getOrDefault(s ,0) + 1);
}
//将元素放入堆，保持堆大小不超k
for(Map.Entry<String, Integer> entry : countMap.entrySet()) {
heap.offer(new Pair<>(entry.getKey(),entry.getValue()));
if(heap.size() > k) {
heap.poll();
}
}
//收集结果并逆序
List<String> result = new ArrayList<String>();
while(!heap.isEmpty()) {
result.add(heap.poll().getKey());
}
Collections.reverse(result);
return result;
}
}
四、295. 数据流的中位数求解
题目链接：295. 数据流的中位数
题目描述：
- 需实现一个类，能初始化、添加元素，并在添加后快速获取数据流的中位数。
题目解析：
- 通过维护大根堆和小根堆，根据元素个数调整堆的分布，从而快速得到中位数。
解题思路：
- 维护大根堆（存前半部分元素）和小根堆（存后半部分元素），根据插入元素的大小和堆的情况调整元素分布，保证元素个数为偶数时两堆平衡，奇数时一堆多一个元素。
解题代码：
//时间复杂度：O(LogN)
//空间复杂度：O(N)
class MedianFinder {
//记录元素个数
int elementCount = 0;
//大根堆存储前半部分元素
PriorityQueue<Integer> maxHeap;
//小根堆存储后半部分元素
PriorityQueue<Integer> minHeap;
public MedianFinder() {
maxHeap = new PriorityQueue<>((a,b) ->{
return b - a;
});
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
elementCount++;
if(elementCount == 1 ) {
maxHeap.offer(num);
return;
}
//元素个数为偶数且当前数大于大根堆堆顶
if(elementCount % 2 == 0 && maxHeap.peek() <= num) {
if(maxHeap.size() < minHeap.size()) {
if(!minHeap.isEmpty() && minHeap.peek() >= num) {
maxHeap.offer(num);
}else {
int temp = minHeap.poll();
maxHeap.offer(temp);
minHeap.offer(num);
}
}else {
minHeap.offer(num);
}
return;
}
//元素个数为偶数且当前数小于大根堆堆顶
if(elementCount % 2 == 0 && maxHeap.peek() > num) {
if(maxHeap.size() < minHeap.size()) {
maxHeap.offer(num);
}else {
int temp = maxHeap.poll();
maxHeap.offer(num);
minHeap.offer(temp);
}
return;
}
//元素个数为奇数且当前数小于大根堆堆顶
if(elementCount % 2 != 0 && maxHeap.peek() >= num) {
maxHeap.offer(num);
} else {
minHeap.offer(num);
}
}
public double findMedian() {
if(elementCount % 2 == 0) {
return (double)((maxHeap.peek() + minHeap.peek())/ 2.0);
}
if(maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else {
return minHeap.peek();
}
}
}
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/12847.html
