优先队列(Priority Queue)是一种抽象数据类型,它类似于队列(Queue),但是每个元素都有一个关联的优先级。在优先队列中,元素按照优先级从高到低(或从低到高)排列,高优先级的元素先出队。这种数据结构可以用堆(Heap)来实现。
堆是一种二叉树结构,有两种主要类型:最大堆和最小堆。在最大堆中,每个节点的值都大于或等于其子节点的值;而在最小堆中,每个节点的值都小于或等于其子节点的值。对于优先队列来说,最大堆常常用于实现。
在堆中,根节点的元素具有最高(或最低)优先级,而且这一性质对于整个堆中的每个节点都成立。这确保了当我们从堆中移除元素时,总是移除具有最高(或最低)优先级的元素。
优先队列的常见操作包括:
- 插入(Insertion):将元素插入队列中。
- 删除最大(或最小)元素:移除并返回队列中具有最高(或最低)优先级的元素。
堆的实现可以通过数组或链表等数据结构。在使用数组实现堆时,父节点和子节点之间的关系可以通过数组的索引关系来表示。在C++中,可以使用 std::priority_queue
来实现优先队列,它默认使用最大堆,也可以通过传递自定义比较函数来实现最小堆。
01.最后一块石头的重量
题目链接:https://leetcode.cn/problems/last-stone-weight/
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x
和 y
,且 x <= y
。那么粉碎的可能结果如下:
- 如果
x == y
,那么两块石头都会被完全粉碎; - 如果
x != y
,那么重量为x
的石头将会完全粉碎,而重量为y
的石头新重量为y-x
。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0
。
示例:
输入:[2,7,4,1,8,1]
输出:1
解释:
先选出 7 和 8,得到 1,所以数组转换为 [2,4,1,1,1],
再选出 2 和 4,得到 2,所以数组转换为 [2,1,1,1],
接着是 2 和 1,得到 1,所以数组转换为 [1,1,1],
最后选出 1 和 1,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
思路
我们可以每次拿出最大的两个相比较,有差值就将差值保留,相等就都粉碎,这样我们很容易想到使用堆去计算,因为这符合堆的特性,我们可以使用各语言库中的堆容器来计算。
-
创建最大堆(Max Heap): 通过
priority_queue<int>
创建一个默认为最大堆的优先队列,将给定的石头数组中的元素加入最大堆中。 - 迭代处理: 使用一个循环迭代处理,直到堆中剩余的元素个数小于等于1。
- 从堆中取出两个最大的元素,执行碎石操作: 每次取出堆中的两个最大元素(即石头的重量最大的两块),执行碎石操作,计算碎石后的重量,将结果加回堆中。
- 返回结果: 当循环结束时,堆中剩余的元素即为最后一块石头的重量,或者堆为空,返回相应的结果。
代码文章来源地址https://www.toymoban.com/news/detail-835012.html
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> heap;
for(int x:stones) heap.push(x);
while(heap.size()>1){
int a=heap.top(); heap.pop();
int b=heap.top(); heap.pop();
if(a>b) heap.push(a-b);
}
return heap.size()?heap.top():0;
}
};
02.数据流中的第 K 大元素
题目链接:https://leetcode.cn/problems/kth-largest-element-in-a-stream/
设计一个找到数据流中第 k
大元素的类(class)。注意是排序后的第 k
大元素,不是第 k
个不同的元素。
请实现 KthLargest
类:
-
KthLargest(int k, int[] nums)
使用整数k
和整数流nums
初始化对象。 -
int add(int val)
将val
插入数据流nums
后,返回当前数据流中第k
大的元素。
示例:
输入:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出:
[null, 4, 5, 5, 8, 8]
解释:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
提示:
1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
- 最多调用
add
方法104
次 - 题目数据保证,在查找第
k
大元素时,数组中至少有k
个元素
思路
这里是典型的topk
问题,找的是第k个大的数,所以我们使用一个k大的小堆就能很好的解决这个问题。
在构造函数中,将初始的元素加入最小堆中,并维护堆的大小为 K,保证堆中只有前 K 大的元素。
当有新元素加入时,将新元素加入最小堆中,然后检查堆的大小是否超过 K,如果超过则弹出堆顶元素。最终返回当前堆顶元素,即为第 K 大的元素。这样,通过不断地将新元素加入最小堆,并保持堆的大小为 K,可以在 add 操作后始终保持堆中的元素为前 K 大的元素,而堆顶元素即为第 K 大的元素。
代码
class KthLargest {
priority_queue<int,vector<int>,greater<int>> heap;
int _k;
public:
KthLargest(int k, vector<int>& nums) {
_k=k;
for(int& x:nums){
heap.push(x);
if(heap.size()>k) heap.pop();
}
}
int add(int val) {
heap.push(val);
if(heap.size()>_k) heap.pop();
return heap.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
03.前K个高频单词
题目链接:https://leetcode.cn/problems/top-k-frequent-words/
给定一个单词列表 words
和一个整数 k
,返回前 k
个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。
示例 1:
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
注意,按字母顺序 "i" 在 "love" 之前。
示例 2:
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词,
出现次数依次为 4, 3, 2 和 1 次。
注意:
1 <= words.length <= 500
1 <= words[i] <= 10
-
words[i]
由小写英文字母组成。 -
k
的取值范围是[1, **不同** words[i] 的数量]
**进阶:**尝试以 O(n log k)
时间复杂度和 O(n)
空间复杂度解决。
思路
很显然这里这是还是topk
问题,还是使用堆来解决问题,但是这里有两个比较条件,所以我们要注意比较函数的实现,主逻辑是找出前k个出现次数最多的,所以整体我们建小堆,还有一个附属条件,次数相同时,字典序小的排在前面,所以在相同次数时,我们相对于字符串建大堆,将字母小的排在前面。
-
哈希表统计频率: 使用
unordered_map
哈希表记录每个字符串出现的频率。 -
优先队列: 使用一个自定义的比较函数对象
cmp
作为优先队列的比较规则。按照频率从大到小排序,若频率相同则按照字符串字典序从小到大排序。遍历哈希表,将每个键值对(字符串及其频率)加入最小堆,并保持堆的大小为 K,当堆的大小超过 K 时,弹出堆顶元素。 - 结果处理: 从堆中依次取出前 K 高的字符串,存储到结果数组中。
最终,返回存储前 K 高字符串的结果数组 ret
。这样通过哈希表统计频率,并使用优先队列来维护前 K 高的频率,实现了找出频率前 K 高的字符串。
代码
class Solution {
struct cmp{
bool operator()(const pair<string,int>& a,const pair<string,int>& b){
if(a.second==b.second) return a.first<b.first;
return a.second>b.second;
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string,int> hash;
for(string& s:words) hash[s]++;
priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> heap;
for(const pair<string,int>& x:hash){
heap.push(x);
if(heap.size()>k) heap.pop();
}
vector<string> ret(k);
for(int i=k-1;i>=0;--i){
ret[i]=heap.top().first;
heap.pop();
}
return ret;
}
};
04.数据流的中位数
题目链接:https://leetcode.cn/problems/find-median-from-data-stream/
中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。
- 例如
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
提示:
-105 <= num <= 105
- 在调用
findMedian
之前,数据结构中至少有一个元素 - 最多
5 * 104
次调用addNum
和findMedian
思路
这里我们最容易想到的暴力解法就是每次插入时排序,但是这种方法时间复杂度太高,其实这里我们可以使用一个大堆和一个小堆来维护所有数,各分一半数据,若两边长度相等,则返回两个堆顶相加除2的值,若不等,返回大堆堆顶即可。
在构造函数中初始化两个优先队列,left
用于存放较小的一半元素(最大堆),right
用于存放较大的一半元素(最小堆)。 在 addNum
方法中,根据元素的大小选择将其插入到左堆或右堆。插入后需要保持两个堆的大小差不超过 1,以确保中位数的计算。 在 findMedian
方法中,根据两个堆的大小关系返回中位数。通过这种方式,不断将数据插入到两个堆中,并保持它们的大小差不超过 1,就能够在 O(1) 时间内查找到当前数据流的中位数。文章来源:https://www.toymoban.com/news/detail-835012.html
代码
class MedianFinder {
priority_queue<int> left;
priority_queue<int,vector<int>,greater<int>> right;
public:
MedianFinder() {}
void addNum(int num) {
if(left.size()==right.size()){
if(left.empty()||num<=left.top()) left.push(num);
else{
right.push(num);
left.push(right.top());
right.pop();
}
}
else{
if(num<=left.top()){
left.push(num);
right.push(left.top());
left.pop();
}else right.push(num);
}
}
double findMedian() {
if(left.size()==right.size()) return (left.top()+right.top())/2.0;
return left.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
到了这里,关于算法沉淀——优先级队列(堆)(leetcode真题剖析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!