Priority_queue - Question 5

692. Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Constraints:

1 <= words.length <= 500

1 <= words[i] <= 10

words[i] consists of lowercase English letters.

k is in the range [1, The number of unique words[i]]

Analysis:

This question is quite straightforward. We can use a priority_queue to keep the top K valid elements.

One difficulty may be about the comparator of the priority_queue. 

In C++, the default order of the priority_queue is with the largest one on the top. But in this question, we need choose the top K with the largest count, so we need a reversed priority_queue. And more, for the same count, we need to choose the one with the lexicographical order.

So we need to take care of this in the comparator.

See the code below:

class Solution {
public:
    typedef pair<int, string> pr;
    struct comparator {
        bool operator() (pr const &a, pr const &b) {
            if(a.first == b.first) return a.second < b.second;
            return a.first > b.first;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        vector<string> res;
        unordered_map<string, int> mp;
        for(auto &a : words) ++mp[a];
        priority_queue<pr, vector<pr>, comparator> pq;
        for(auto &a : mp) {
            pq.push({a.second, a.first});
            if(pq.size() > k) pq.pop();
        }
        while(pq.size()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Upper Layer