算法练习——优先级队列

一：最后一块石头的重量

题目要求：

解题思路：

思路：

创建一个优先级队列，其底层为堆结构，将数组中所有数据入堆，默认情况下为大堆。大堆创建完毕后，循环取两次堆顶元素做判断是否再次入堆，直至堆中元素小于等于1

此时出循环会有两种情况，一种情况是：

堆中没有元素，表示最后一次循环中，两个石头大小相等抵消，没有新的元素入堆

堆中有一个元素，则是题目要求的最后一块石头重量

实现代码：

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> pq;for(auto& s : stones){pq.push(s);}while(pq.size() > 1){int x = pq.top();pq.pop();int y = pq.top();pq.pop();if(x - y != 0) pq.push(x-y);}return pq.size() ? pq.top() : 0;}
};

二：数据流中第K大的数

题目要求：

解题思路：

思路：

这类问题统称为Top_K问题

对于判断第K大或者前K大，都是建立小堆。

对于第K大，我们就创立个数为K个的小堆，堆顶即为第K大

对于前K大，我们只要创立个数为K的小堆，然后去遍历数组，将满足结果的入堆，然后出堆，维护这个堆即可

对于判断第K小或者前K小，都是建立大堆。

对于第K小，我们就创立个数为K的大堆，堆顶即为第K小

对于前K小，我们只需创立个数为K的大堆，然后遍历数组，在遍历的过程去维护大堆即可

实现代码：

class KthLargest {
public:KthLargest(int k, vector<int>& nums) :_k(k){for(auto& n : nums){_heap.push(n);if(_heap.size() > _k) _heap.pop();}}int add(int val) {_heap.push(val);if(_heap.size() > _k) _heap.pop();return _heap.top();}priority_queue<int,vector<int>,greater<int>> _heap;int _k;
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

三：前K个高频单词

题目要求：

解题思路：

思路：

借助哈希表统计每个单词出现的个数，并记录于 unordered_map<string, int> hash; 中

和上一题类似，本题也属于Top_K问题中，前K个大一类，因此我们需要创建一个堆中数据个数为K的小堆，然后遍历哈希表来维护这个小堆。具体做法为：若比堆顶数据大，则入堆，若堆中数据个数大于K，则出堆。

实现代码：

class Solution {
public:struct Com{bool operator()(const pair<string,int>& x1, const pair<string,int>& x2){return x1.second > x2.second || (x1.second == x2.second && x1.first < x2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> hash;for(auto& str : words){hash[str]++;}priority_queue<pair<string,int>,vector<pair<string,int>>,Com> heap;for(auto& str : hash){heap.push(str);if(heap.size() > k) heap.pop();}vector<string> ret;while(heap.size()){ret.emplace_back(heap.top().first);heap.pop();}reverse(ret.begin(),ret.end());return ret;}
};

四：数据流中的中位数

题目要求：

解题思路：

思路：如果要找寻有序数据中的中位数，比较好的做法是：建立一个大堆和小堆来维护这组数据。

假设这组数从左到右依次按顺序排列：

我们将数据分成两段来看，前一段为较小的数，这段数建立大堆，因此堆顶恰好是这组数中最大的值，维持大堆的数据个数为m

后一段为较大的数，这段建立小堆，因此堆顶恰好是这组数中最小的值，维持小堆的数据个数为n

当m = n 时：中位数恰好是（大堆堆顶+小堆堆顶）/ 2

当m = n+1，即大堆个数比小堆多一个时，中位数恰好是大堆堆顶元素

因此我们在遍历数组arr时，需要保证m == n 或者 m == n+1

遍历原数组arr(假设当前值为num):

①当 m = n 时，先判空

Ⅰ：若 m.top() >= num; num 入左边大堆，此时 m == n + 1；

Ⅱ：否则入右边小堆，此时 m != n + 1; 为了维护 m = n+1，需将右边小堆堆顶元素入左边大堆(右边小堆保证了堆顶元素为较小值)，然后右边小堆在出堆(维护 m = n+1)

②当 m = n + 1时:

Ⅰ：若 m.top() < num; num 入右边小堆，此时 m == n ；

Ⅱ：否则入左边大堆，此时 m != n + 1; 为了维护 m = n+1，需将左边大堆堆顶元素入右边小堆(左边大堆保证了堆顶元素为较大值)，然后左边大堆在出堆(维护 m = n)

实现代码：

class MedianFinder {
public:MedianFinder() {}void addNum(int num) {if(_left.size() == _right.size()){if(_left.size() == 0 || _left.top() >= num) _left.push(num);else if (_right.size() == 0 || _left.top() < num) {_right.push(num);_left.push(_right.top());_right.pop();}}else{if(_left.top() < num) _right.push(num);else {_left.push(num);_right.push(_left.top());_left.pop();}}}double findMedian() {if(_right.size() == _left.size())   return (_right.top() + _left.top()) / 2.0;else return _left.top();}
private:priority_queue<int> _left;priority_queue<int,vector<int>,greater<int>> _right;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/