O(nlog(k)) Priority Queue C++ code


  • 4
    X
    class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            unordered_map<string, int> freq;
            for(auto w : words){
                freq[w]++;
            }
            
            auto comp = [&](const pair<string,int>& a, const pair<string,int>& b) {
                return a.second > b.second || (a.second == b.second && a.first < b.first);
            };
            typedef priority_queue< pair<string,int>, vector<pair<string,int>>, decltype(comp) > my_priority_queue_t;
            my_priority_queue_t  pq(comp);
            
            for(auto w : freq ){
                pq.emplace(w.first, w.second);
                if(pq.size()>k) pq.pop();
            }
            
            vector<string> output;
            while(!pq.empty()){
                output.insert(output.begin(), pq.top().first);
                pq.pop();
            }
            return output;
        }
    };
    

  • 0
    S
            while(!pq.empty()){
                output.insert(output.begin(), pq.top().first);
                pq.pop();
            }
    

    Inserting at the beginning of a vector with n elements takes O(n) time.

    So technically this takes O(nlog(k) + k^2) time.

    A better way might be to insert at the end (O(1) amortized time for each insert at the end), then reverse the output vector after the while loop.


  • 0
    M

    Same idea but using a struct as the comparator

    class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            unordered_map<string,int> dict;
            for(const string& s:words) dict[s]++;
            
            priority_queue<pair<string,int>, vector<pair<string,int>>, Comp> pq;
            for(const auto& pa:dict) {
                pq.push(pa);
                if(pq.size()>k) pq.pop();
            }    
            
            vector<string> result;
            while(!pq.empty()) {
                result.push_back(pq.top().first);
                pq.pop();
            }
            reverse(result.begin(),result.end());    
            return result;    
        }
    private:
        struct Comp {
            Comp() {}
            ~Comp() {}
            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);
            }
        };
    
    };
    

Log in to reply
 

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