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

前言

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

最后一块石头重量

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

题目要求

题目解析

代码如下

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/

题目要求

题目解析

代码如下

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/

题目要求

题目解析

当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/

题目要求

题目解析

这里可以用一个大小堆，小堆中的元素每个都比大堆中的元素大，每当数据来的时候，判断与大小堆顶的关系，插入到对应的堆中，需要注意的是还要维持大小堆中的元素个数，只有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 + 1
                int 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();
 */