Priority queue 排序找前最大K个元素 类型

priority queue 实现的数据结构是红黑树,balanced binary search tree。

471. Top K Frequent Words
Code(Language:C++) (Judger:ip-172-31-12-4)
class Solution {
public:
    /**
     * @param words: an array of string
     * @param k: An integer
     * @return: an array of string
     */
    struct cmp{
        bool operator()(const pair<string, int> &a, const pair<string, int> &b){
            return a.second > b.second || (a.second == b.second && a.first < b.first); 
        } 
    }; 
    vector<string> topKFrequentWords(vector<string> &words, int k) {
        // write your code here
        unordered_map<string, int> mp;
        for(auto s : words){
            mp[s]++; 
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq; 
        for(auto i : mp){
            pq.push({i.first, i.second});
            if(pq.size() > k){
                pq.pop(); 
            }
        }
        vector<string> res; 
        while(!pq.empty()){
            res.push_back(pq.top().first);
            pq.pop(); 
        }
        reverse(res.begin(), res.end());
        return res; 
    }
};

Comments

Popular posts from this blog

Amazon OA 763. Partition Labels

1427. Split Array into Fibonacci Sequence

05/25 周一