【算法刷题指南】优先级队列

🌈个人主页： 南桥几晴秋
🌈C++专栏： 南桥谈C++
🌈C语言专栏： C语言学习系列
🌈Linux学习专栏： 南桥谈Linux
🌈数据结构学习专栏： 数据结构杂谈
🌈数据库学习专栏： 南桥谈MySQL
🌈Qt学习专栏： 南桥谈Qt
🌈菜鸡代码练习： 练习随想记录
🌈git学习： 南桥谈Git

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 本科在读菜鸡一枚，指出问题及时改正

---

---

1046.最后一块石头的重量

1046.最后一块石头的重量

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for(auto 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;}
};

---

703.数据流中的第k大元素

703.数据流中的第k大元素

class KthLargest {priority_queue<int,vector<int>,greater<int>> heap;int _k;
public:KthLargest(int k, vector<int>& nums) {_k=k;for(auto 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);*/

---

692.前K个高频单词

692.前K个高频单词

class Solution {typedef pair<string,int> PSI;struct cmp{bool operator()(const PSI& a,const PSI& 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(auto &s:words) hash[s]++;priority_queue<PSI,vector<PSI>,cmp> heap;for(auto &pis:hash){heap.push(pis);if(heap.size()>k) heap.pop();}vector<string> ans(k);for(int i=k-1;i>=0;i--){ans[i]=heap.top().first;heap.pop();}return ans;}
};

---

295. 数据流的中位数

295. 数据流的中位数

二分查找+插入排序

#include<algorithm>
#include<vector>
class MedianFinder {
public:MedianFinder() {}vector<int> newarr;void addNum(int num) {auto it=lower_bound(newarr.begin(),newarr.end(),num);newarr.insert(it,num);}double findMedian() {int n=newarr.size();if(n%2==1) return newarr[n/2];else return  (newarr[n / 2 - 1] + newarr[n / 2]) / 2.0;}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

优先队列

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;else 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();*/

---