当前位置：首页 > article >正文

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

article 2024/12/5 3:27:21

在这里插入图片描述

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

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

文章目录

1046.最后一块石头的重量
703.数据流中的第k大元素
692.前K个高频单词
295. 数据流的中位数

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大元素

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个高频单词

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. 数据流的中位数

二分查找+插入排序

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