C++ 16ms O(nlogk) time and O(n) extra space solution


  • 0
    class Compare {
    public:
        bool operator() (const pair<string, int>& a, const pair<string, int>& b) const {
            if (a.second == b.second)
                return a.first < b.first;
            else return a.second > b.second;
        }
    };
    
    class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            unordered_map<string, int> mapping;
            priority_queue<pair<string, int>, 
                           vector<pair<string, int>>, 
                           Compare> pq;
            for (auto& word : words) {
                if (mapping.count(word) == 0)
                    mapping[word] = 1;
                else mapping[word]++;
            }
            for (auto it = mapping.begin(); it != mapping.end(); ++it) {
                if (pq.size() < k)
                    pq.push(*it);
                else {
                    auto currMin = pq.top();
                    if (currMin.second < it->second) {
                        pq.pop();
                        pq.push(*it);
                    }
                    else if (currMin.second == it->second) {
                        if (currMin.first > it->first) {
                            pq.pop();
                            pq.push(*it);
                        }
                    }
                }
            }
            vector<string> res(k);
            int i = k - 1;
            while (!pq.empty()) {
                res[i] = pq.top().first;
                pq.pop();
                i--;
            }
            return res;
        }
    };
    

    Comments are welcome.


  • 0
    X

    I don't think that using unordered_map can satisfy O(n) space. In fact, it always requests much space from OS.


  • 0

    @xu.2727
    In my opinion, O(n) means linear increasing with increment = n * some constant number. If the map size is not such linear increasing, then what it should be?


  • 0
    E

    I have the same thought with you. I think this is O(nlogk) time and O(n) space. One suggestion is that since you have defined a class for comparing you do not need to rewrite the comparing function again in your for loop.

    Here is my code.

    class Solution {
        struct cmp {
            bool operator()(const pair<int, string>& one, const pair<int, string>& two) const {
                return one.first > two.first ||(one.first == two.first && one.second < two.second);
            }
        };
        
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            unordered_map<string, int> word2Freq;
            vector<string> res(k);
            for (auto& w : words) word2Freq[w]++;
            priority_queue<pair<int, string>, vector<pair<int, string> >, cmp> heap;
            cmp obj;
            for (auto it = word2Freq.begin(); it != word2Freq.end(); it++) {
                pair<int, string> cur = make_pair(it->second, it->first);
                if (heap.size() < k) {
                    heap.push(cur);
                } else if (!obj(heap.top(), cur)) {
                    heap.pop();
                    heap.push(cur);
                } 
            }
            int it = k - 1;
            while (!heap.empty()) {
                res[it--] = heap.top().second;
                heap.pop();
            }
            return res;
        }
    };
    

Log in to reply
 

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