💁♂️个人主页：进击的荆棘
👇作者其它专栏：
《数据结构与算法》《算法》《C++起始之路》
相关题解
1.最后一块石头的重量
算法思路：
其实就是一个模拟的过程：
●每次从石堆中拿出最大的元素以及次大的元素，然后将它们粉碎；
●若还有剩余，就将剩余的石头继续放在原始的石堆里。
重复上面的操作，直到石堆里只剩下一个元素，或没有元素（因为所有的石头可能全部抵消了）
那么主要解决的问题是：
●如何顺利的拿出最大的石头以及次大的石头；
●并且将粉碎后的石头放入石堆中之后，也能快速找到下一轮粉碎的最大石头和次大石头。
这正好满足堆的特性：
●可以创建一个大根堆；
●然后将所有的石头放入大根堆中；
●每次拿出前两个堆顶元素粉碎一下，若还有剩余，就将剩余的石头继续放入堆中；
这样就能快速的模拟出这个过程。
class Solution { public: int lastStoneWeight(vector<int>& stones) { priority_queue<int> heap; for(auto& e:stones) heap.push(e); while(heap.size()>=2){ int y=0,x=0; y=heap.top(); heap.pop(); x=heap.top(); heap.pop(); if(y>x) heap.push(y-x); } return heap.size()==1?heap.top():0; } };2.数据流中的第 K 大元素
算法思路：
Topk是堆的经典问题，可以想到用堆来模拟。
class KthLargest { //创建一个大小为k的小根堆 priority_queue<int,vector<int>,greater<int>> heap; int _k; public: KthLargest(int k, vector<int>& nums) { _k=k; for(auto& e:nums){ heap.push(e); 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); */3.前K个高频单词
算法思路：
●稍微处理一下原数组：
a.需要知道每一个单词出现的频次，因此可以先使用哈希表，统计出每一个单词出现的频次；
b.然后在哈希表中，选出前k大的单词（为什么不再原数组中选？因为原数组中存在重复的单词，哈希表里没有重复单词，并且还有每一个单词出现的频次）
●如何使用堆，拿出前k大元素：
a.先定义一个自定义排序，需要的是前k大，因此需要一个小根堆。但是当两个字符串频次相同的时候，需要的是字典序较小的，因此是一个大根堆的属性，在定义比较器的时候需要注意；
▢当两个字符串出现频次不同的时候：需要的是基于频次比较的小根堆
▢当两个字符串出现频次相同的时候：需要的是基于字典序比较的大根堆
b.定义好比较器之后，依次将哈希表中的字符串插入到堆中，维持堆中的元素不超过k个；
c.遍历完整个哈希表后，堆中剩余的元素就是前k大的元素。
class Solution { typedef pair<string,int> PSI; struct Compare{ bool operator()(const PSI& p1,const PSI& p2){ if(p1.second==p2.second){//频次相同按照大根堆的方式存 return p1.first<p2.first; } return p1.second>p2.second; } }; public: vector<string> topKFrequent(vector<string>& words, int k) { //1.统计每个单词的频次 unordered_map<string,int> hash; for(auto& str:words) hash[str]++; //2.创建一个大小为k的堆 priority_queue<PSI,vector<PSI>,Compare> pq; //topk的主逻辑 for(auto psi:hash){ pq.push(psi); if(pq.size()>k) pq.pop(); } //提取结果 vector<string> ret(k); for(int i=k-1;i>=0;i--){ ret[i]=pq.top().first; pq.pop(); } return ret; } };4.数据流的中位数
算法思路（利用两个堆）：
这是一道关于【堆】这种数据结构的一个【经典应用】。
可以将整个数组【按照大小】平分为两部分（若不能平分，就让较小部分的元素多一个），较小部分称为左侧部分，较大部分称为右侧部分：
●将左侧部分放入【大根堆】中，然后将右侧部分放入【小根堆】中；
●这样就能在O（1）时间内拿到中间的一个数或两个数，进而求平均数。
若下图：
于是问题就变成了【如何将一个一个从数据流中过来的数据，动态调整到大根堆或小根堆中，并且保证两个堆的元素一致，或左侧堆的元素比右侧堆的元素多一个】
为了方便叙述，将左侧的【大根堆】记为_left，右侧的【小根堆】记为_right，数据量中来的数据记为num。
其实就是一个【分类讨论】的过程：
1.若左右堆的【数量相同】，_left.size()==_right.size()：
a.若两个堆都是空的，直接将数据num放入到_left中；
b.若两个堆非空：
i.若元素要放入左侧，也就是num<=_left.top()：就直接放，因为不会影响我们制定的规则；
ii.若放入右侧
●可以先将num放入_right中，
●然后把_right的堆顶元素放入_left中；
2.若左右堆的数量【不相同】，就是_left.size()>_right.size():
a.此时问题是num是否会放入_left中，导致_left变得过多：
i.若num放入_right中，若num>=_right.top()，直接放；
ii.反之，就是需要放入_left中：
●可以先将num放入_left中，
●然后把_left的堆顶元素放入_right中；
只有每一个新来的元素按照【上述规则】执行，就能保证_left中放着整数数组排序后的【左半部分】，_right中放着整个数组排序后的【右半部分】，就能在O（1）的时间内求出平均数。
class MedianFinder { //用两个堆来维护数据流的中位数 //大根堆 priority_queue<int> _left; //小根堆 priority_queue<int,vector<int>,greater<int>> _right; public: MedianFinder() { } void addNum(int num) { //1.当_left.size()==_right.size() if(_left.size()==_right.size()){ //若num小于等于_left堆顶元素或_left为空时 if(_left.empty()||_left.top()>=num){ _left.push(num); } else{ //先将num压入_right,再将多出的元素压到_left _right.push(num); _left.push(_right.top()); _right.pop(); } } //2.当_left.size()>_right.size()即_left.size()=_right.size()+1 else{ //若num小于等于_left堆顶元素时 if(_left.top()>=num){ //此时_left比_right个数多2，先将num压入_left，再将多出的元素入_right _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(); */
