C++ Solution with min heap (89.56%)


  • 0
    M
    class Cell {
    public:
        string word;
        int times;
        Cell(int t, string w): word(w), times(t) {}
    };
    
    struct comp {
        bool operator() (const Cell& a, const Cell& b) {
            if (a.times == b.times) {
                return a.word < b.word;
            }
            return a.times > b.times;
        }
    };
    
    class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            unordered_map<string, int> count;
            for (auto w : words) { count[w]++; }
            priority_queue<Cell, vector<Cell>, comp> pq; // minheap
            vector<string> res;
            
            auto it = count.begin();
            for (int i = 0; i < k; i++, it++) {
                pq.push(Cell(it->second, it->first));
            }
            
            for(; it != count.end(); it++) {
                Cell newCell(it->second, it->first);
                if (comp()(newCell, pq.top())) {
                    pq.pop();
                    pq.push(newCell);
                }
            }
            
            while (!pq.empty()) {
                res.push_back(pq.top().word);
                pq.pop();
            }
            
            reverse(res.begin(), res.end());
            return res;
        }
    };
    

Log in to reply
 

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