Given a list of words and an integer k, return the top k frequent words in the list.

Notice

You should order the words by the frequency of them in the return list, the most frequent one comes first. If two words has the same frequency, the one with lower alphabetical order come first.

Have you met this question in a real interview?

Yes

Example

Given

[
    "yes", "lint", "code",
    "yes", "code", "baby",
    "you", "baby", "chrome",
    "safari", "lint", "code",
    "body", "lint", "code"
]

for k =3, return["code", "lint", "baby"].

for k =4, return["code", "lint", "baby", "yes"],

Challenge

Do it in O(nlogk) time and O(n) extra space.

Extra points if you can do it in O(n) time with O(k) extra space approximation algorithms.

class Solution {
public:
    /**
     * @param words an array of string
     * @param k an integer
     * @return an array of string
     */
    vector<string> topKFrequentWords(vector<string>& words, int k) {
        // Write your code here
        unordered_map<string, int> hash;
        for (string& word : words) {
            ++hash[word];
        }

        priority_queue<Node> q;
        for (auto it : hash) {
            q.push(Node(it.second, it.first));
        }

        vector<string> res;
        int n = q.size();
        for (int i = 0; i < k && i < n; ++i) {
            res.push_back(q.top().word);
            q.pop();
        }
        return res;
    }


    class Node {
    public:
        int freq;
        string word;
        Node(int _freq, string _word) : freq(_freq), word(_word) {};
        bool operator<(const Node& other) const {
            if (freq == other.freq) {
                return word > other.word;
            }
            return freq < other.freq;
        }
    };
};