Priority queue c++


  • 0
    A

    class compare{
    public:
    bool operator()(pair<int,string> &a,pair<int,string> &b){
    if(a.first!=b.first)
    return a.first>b.first;
    else
    return a.second<b.second;
    }
    };
    class Solution {
    public:

    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> mp;
        for(int i=0;i<words.size();i++){
            mp[words[i]]++;
        }
        vector<pair<int,string> > sol;
        map<string,int> ::iterator it;
        //heap of size k
        priority_queue<pair<int,string> ,vector<pair<int,string> >,compare> q;
        int count=0;
        for(it=mp.begin();it!=mp.end();it++){
            if(count==k)
                break;
           q.push(make_pair(it->second,it->first));
            count++;
        }
        
        for(;it!=mp.end();it++){
            if((it->second)>(q.top().first)){
                q.pop();
                q.push(make_pair(it->second,it->first));
            }
        }
        
        while(!q.empty()){
            sol.push_back(q.top());
            q.pop();
        }
        
        reverse(sol.begin(),sol.end());
        vector<string> ans;
        for(int i=0;i<sol.size();i++)
            ans.push_back(sol[i].second);
        return ans;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.