Top K Frequent Words trong C++

Cho danh sách từ không rỗng, tìm k từ xuất hiện nhiều nhất. Kết quả sắp xếp theo tần suất giảm dần, nếu tần suất bằng nhau thì từ theo thứ tự bảng chữ cái nhỏ hơn đứng trước.

Ví dụ: ["the","sky","is","blue","the","weather","is","comfortable"], k=3 → ["is","the","blue"].

Giải thuật

• Dùng map đếm tần suất.
• Dùng priority_queue với comparator tùy chỉnh: tần suất giảm, từ tăng.
• Duyệt map, đẩy vào queue giữ kích thước k.
• Lấy kết quả từ queue, đảo ngược để có thứ tự đúng.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

struct Comparator {
    bool operator()(pair<string,int> a, pair<string,int> b) {
        if (a.second != b.second) return a.second > b.second; // min-heap theo tần suất
        return a.first < b.first; // nếu tần suất bằng, từ lớn hơn ưu tiên (để pop)
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> m;
        for (auto& w : words) m[w]++;
        priority_queue<pair<string,int>, vector<pair<string,int>>, Comparator> pq;
        for (auto& p : m) {
            if (pq.size() < k) pq.push(p);
            else if (pq.top().second < p.second || (pq.top().second == p.second && pq.top().first > p.first)) {
                pq.pop();
                pq.push(p);
            }
        }
        vector<string> res;
        while (!pq.empty()) {
            res.push_back(pq.top().first);
            pq.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"the","sky","is","blue","the","weather","is","comfortable"};
    for (auto& s : ob.topKFrequent(v, 3)) cout << s << " ";
    return 0;
}

Input

["the","sky","is","blue","the","weather","is","comfortable"] 3

Output

is the blue