Top K Frequent Words

top-k-frequent-words.cpp

// https://leetcode.com/problems/top-k-frequent-words

struct Solution final {
    static vector<string> topKFrequent(vector<string>& words, int k) noexcept {
        unordered_map<string, int> tally(words.size());
        auto it = words.begin();
        for (auto& w : words) if (!tally[w]--) swap(*it++, w);
        words.resize(tally.size());
        const auto compare = [&tally](const string& a, const string& b) __attribute__((always_inline)) noexcept {
            return tie(tally[a], a) < tie(tally[b], b);
        };
        if (k == 1) {
            iter_swap(words.begin(), min_element(words.begin(), words.end(), compare));
            words.resize(1);
            return words;
        }
        nth_element(words.begin(), words.begin() + (k - 1), words.end(), compare);
        words.resize(k);
        sort(words.begin(), words.end(), compare);
        return words;
    }
};

static const auto speedup = []() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();