Top K Frequent Words ใน C++

ตัวอย่าง: words = ["the","sky","is","blue","the","weather","is","comfortable"], k = 3

ความถี่: the:2, is:2, sky:1, blue:1, weather:1, comfortable:1

ผลลัพธ์: ["is", "the", "blue"] (is และ the ถี่ 2 เท่า is อยู่ก่อน the เพราะ i < t)

อัลกอริทึม: Hash Map + Priority Queue (Min-Heap of size k)

1. นับความถี่แต่ละคำด้วย unordered_map<string, int> → O(n)
2. ใช้ Priority Queue (Min-Heap) ขนาดสูงสุด k:
   • Comparator: ความถี่น้อยกว่าก่อน (min-heap), ถ้าเท่ากัน ตัวอักษรมากกว่าก่อน (เพื่อ pop ตัวที่ "แย่กว่า" ออก)
   • วนทุกคู่ (word, freq) ใน map:
     • push เข้า heap
     • ถ้า heap size > k → pop ตัวน้อยที่สุดออก
3. Pop ทั้งหมดจาก heap เก็บใน vector แล้ว reverse (เพราะ min-heap pop ให้น้อยก่อน)

ตัวอย่างโค้ด C++

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

struct Comparator {
    // min-heap: ความถี่น้อยกว่าก่อน, ถ้าเท่ากัน ตัวอักษรมากกว่าก่อน
    bool operator()(const pair<string, int>& a, const pair<string, int>& b) const {
        if (a.second != b.second) return a.second > b.second; // freq น้อยกว่าก่อน
        return a.first < b.first; // string มากกว่าก่อน (reverse alphabetical)
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq;
        for (const string& w : words) freq[w]++;
        
        priority_queue<pair<string, int>, vector<pair<string, int>>, Comparator> pq;
        
        for (auto& p : freq) {
            pq.push(p);
            if (pq.size() > k) pq.pop();
        }
        
        vector<string> res;
        while (!pq.empty()) {
            res.push_back(pq.top().first);
            pq.pop();
        }
        reverse(res.begin(), res.end()); // min-heap ให้ ascending เราต้องการ descending
        return res;
    }
};

void print_vector(vector<string> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << '"' << v[i] << '"';
        if (i + 1 < v.size()) cout << ", ";
    }
    cout << "]" << endl;
}

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

Input

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

Output

["is", "the", "blue"]

ความซับซ้อน (Complexity)

• เวลา: O(n log k) - n คำ, heap size k
• พื้นที่: O(n) - hash map + heap

วิธีอื่น: ใช้ vector เก็บทุกคู่ แล้ว sort ด้วย comparator แบบ custom → O(n log n) เรียบง่ายกว่า แต่อาจช้ากว่าเล็กน้อยเมื่อ k ≪ n