算法_优先级队列---持续更新

前言

本文将会向你分享优先级队列相关的题目：最后一块石头重量、数据流中的第K大元素、前K个高频单词、数据流的中位数

最后一块石头重量

https://leetcode.cn/problems/last-stone-weight/

题目要求

题目解析

题目要求每次从一堆数中找出最大的两个，然后再进一步判断，最重要的是如何从一堆数中找出最大的数，这时可以想到用大根堆，最大的在堆顶，pop堆顶，就可以拿到次大的了。

代码如下

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;   //优先级队列，默认是一个大根堆for(auto& e : stones){heap.push(e);}while(heap.size() > 1){int x = heap.top(); heap.pop();int y = heap.top(); heap.pop();if(x > y) heap.push(x - y);}return heap.size() ? heap.top() : 0;}
};

数据流中的第K大元素

https://leetcode.cn/problems/jBjn9C/

题目要求

题目解析

题目要求是找到数据流中的第K大元素，那么把这些数据放到一个小根堆中就可以解决，题目有点绕（将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素），其实就是外部调用add函数传入的val 有数据流1，2，3，4。比如需要求第3（K）大的元素，我们知道是2，只需要将小根堆的元素个数维持为3（K）个，那么堆顶元素就是我们需要求的第3大的元素。 也就是当堆里的元素大于K，就pop，这样就能维持堆里的元素等于K

代码如下

class KthLargest {
public:priority_queue<int, vector<int>, greater<int>> heap;int k = 0;KthLargest(int k, vector<int>& nums) {this->k = k;for(auto& e : nums){add(e);}}//确保堆始终包含k个最大的元素，堆顶将是第k大的元素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);*/

前K个高频单词

https://leetcode.cn/problems/top-k-frequent-words/

题目要求

题目解析

题目要求返回前k个出现次数最多的单词，那么很容易想到的是建一个小堆，维持小堆的个数未为k个，堆里剩下的就是次数出现最多的，但是题目中有额外要求，如果单词出现的频次相同，那么就按字典顺序排序。那么我们是需要自定义比较函数的

当second（频次）相同，那么按照字典序排序，也就是小的排在前面，a.first < b.first也就是小的排在前面， a.second > b.second频次大的排在后面

if(a.second == b.second)
{   return a.first < b.first;   //按照字典顺序排序
}
else return a.second > b.second;   

代码如下

class Solution {
public:struct cmp{bool operator()(const pair<string, int>& a, const pair<string, int>& b){//单词出现的频率相同if(a.second == b.second){   return a.first < b.first;   //按照字典顺序排序}else return a.second > b.second;    //小根堆，大的排在下面}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string, int> hash;    //用哈希表统计单词次数for(auto& e : words){hash[e]++;}//TopK,取前k个出现次数最多的单词priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> heap;for(auto& e : hash){heap.push(e);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;}
};

数据流的中位数

https://leetcode.cn/problems/find-median-from-data-stream/

题目要求

题目解析

题目要求实现中位数查找器，直接利用数组的个数/2来求中位数的方式是不够高效的，因为数据流是动态变化的。

这里可以用一个大小堆，小堆中的元素每个都比大堆中的元素大，每当数据来的时候，判断与大小堆顶的关系，插入到对应的堆中，需要注意的是还要维持大小堆中的元素个数，只有maxHeap,size() = minHeap.size() 或者 maxHeap,size() = minHeap.size()+1只有这两种情况才行。因为只有这样，如果数据流的元素个数为奇数，那么就是大堆堆顶，如果是偶数，就手动求一下（大堆堆顶+小堆堆顶）/2即可

ps：这种方法并不好想，这次记住就行啦！

代码如下

class MedianFinder {
public:MedianFinder() {}void addNum(int num) {int sz1 = maxHeap.size(), sz2 = minHeap.size();if(sz1 == sz2){if(sz1 == 0 || num <= maxHeap.top())   //注意sz1 == 0要放到最前面，否则当堆中元素为空时，会空指针maxHeap.push(num); //直接插入else{minHeap.push(num); //此时sz2 == sz1 + 1int tmp = minHeap.top(); minHeap.pop();maxHeap.push(tmp);}}else    //sz1 == sz2+1{if(num <= maxHeap.top()){maxHeap.push(num);int tmp = maxHeap.top(); maxHeap.pop();minHeap.push(tmp);  //维持sz1 == sz2+1}else{minHeap.push(num);  //直接插入}}}double findMedian() {if((maxHeap.size() + minHeap.size()) % 2 == 0)        return static_cast<double>(maxHeap.top() + minHeap.top()) / 2;else return static_cast<double>(maxHeap.top());}
public:priority_queue<int, vector<int>, greater<int>> minHeap;priority_queue<int> maxHeap;
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/