692. Top K Frequent Words

hashmap+bucket sort O(n+k) worst case O(nlogn)
跟347. Top K Frequent Elements思路基本一样

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (const auto &w : words) {
            ++m[w];
        }
        int n = words.size();
        vector<set<string>> buckets(n + 1); // 因为要求按字典序排序所以复杂度会略高
        for (auto [w, freq] : m) {
            buckets[freq].insert(w);
        }
        vector<string> res;
        for (int i = n; i >= 0; --i) {
            for (const auto &w : buckets[i]) {
                res.push_back(w);
                if (size(res) == k) return res;
            }
        }
        return res;
    }
};

hashmap+trie+bucket sort O(n+k*w) time O(n) space w是平均字符长度

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (const auto &w : words) {
            ++m[w];
        }
        int n = words.size();
        vector<TrieNode *> buckets(n + 1, nullptr);
        for (auto&& b : buckets) {
            b = new TrieNode;
        }
        for (const auto &p : m) {
            insert(buckets[p.second], p.first);
        }
        vector<string> res;
        for (int i = n; i >= 0 && k > 0; --i) { // 题目要求高频到低频
            getWords(buckets[i], k, res);
        }
        return res;
    }

    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        bool isEnd = false;
        string w;
    };

    void insert(TrieNode *p, const string &w) {
        for (char c : w) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p = p->children[c - 'a'];
        }
        p->isEnd = true;
        p->w = w;
    }

    void getWords(TrieNode *p, int &k, vector<string> &res) {
        if (!p || k == 0) return;
        if (p->isEnd) {
            res.push_back(p->w);
            --k;
        }
        for (int i = 0; i < 26; ++i) { // trie天然形成字典序
            getWords(p->children[i], k, res);
        }
    }
};

quickselect O(n+klogk) time worst case O(nlogn) O(n) space

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> m;
        for (const auto &w : words) {
            ++m[w];
        }
        vector<pair<string, int>> v(begin(m), end(m));
        auto cmp = [](const auto &a, const auto &b){ return a.second == b.second ? a.first < b.first : a.second > b.second; };
        nth_element(begin(v), begin(v) + k, end(v), cmp);
        sort(begin(v), begin(v) + k, cmp);
        vector<string> res;
        for (const auto &[w, f] : v) {
            res.push_back(w);
            if (size(res) == k) return res;
        }
        return res;
    }
};