Top K Frequent Elements

Bài toán

Cho một mảng số nguyên nums và một số nguyên k. Trả về k phần tử xuất hiện nhiều nhất trong mảng. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Giải thích: số 1 xuất hiện 3 lần, số 2 xuất hiện 2 lần. Đây là 2 số phổ biến nhất.

Phân Tích & Tiếp Cận

Cách 1: Map + Sorting

1. Đếm tần suất mỗi số bằng Hash Map: {1: 3, 2: 2, 3: 1}.
2. Chuyển Map thành mảng các cặp và Sort giảm dần theo tần suất.
3. Lấy k phần tử đầu tiên.

function topKFrequent(nums: number[], k: number): number[] {
    const count: Record<number, number> = {};
    for (const n of nums) {
        count[n] = (count[n] || 0) + 1;
    }

    // Convert to array and Sort: O(N log N)
    const sorted = Object.keys(count).sort((a, b) => count[Number(b)] - count[Number(a)]);
    
    return sorted.slice(0, k).map(Number);
}

• Time Complexity: $O(N \log N)$ do sắp xếp.

Cách 2: Heap (Priority Queue)

Thay vì sort toàn bộ, ta dùng Min-Heap kích thước k.

• Nếu Heap chưa đầy k: push vào.
• Nếu Heap đầy: so sánh phần tử mới với đỉnh Heap (phần tử bé nhất trong top k). Nếu lớn hơn thì pop đỉnh cũ, push cái mới vào.
• Time Complexity: $O(N \log k)$ - Tốt hơn sort toàn bộ nếu $k \ll N$.

(Tuy nhiên, JS không có sẵn Heap/PriorityQueue built-in trong standard library như Java/Python, nên thường trong phỏng vấn JS ta ít dùng cách này trừ khi được phép dùng library ngoài hoặc tự implement Heap).

Cách 3: Bucket Sort (Tối ưu nhất cho JS)

Kỹ thuật này cực hay khi ta biết giới hạn của "Tần suất". Một số chỉ có thể xuất hiện tối đa $N$ lần (nếu mảng toàn là số đó). Thay vì key là số, value là tần suất. Ta đảo ngược tư duy: Tạo một mảng bucket có kích thước $N+1$, trong đó index là Tần suất, và giá trị tại index đó là Danh sách các số có tần suất đó.

Index: 0 | 1 | 2 | 3 | ... | N Val: [] | [3] | [2] | [1] | ... | [] (Số 3 xuất hiện 1 lần, Số 2 xuất hiện 2 lần, Số 1 xuất hiện 3 lần)

Sau đó, ta chỉ cần duyệt ngược từ $N$ về 0. Gặp bucket nào có dữ liệu thì lấy ra cho đến khi đủ k số.

function topKFrequent(nums: number[], k: number): number[] {
    const count = new Map<number, number>();
    const bucket: number[][] = Array.from({ length: nums.length + 1 }, () => []);

    // 1. Đếm tần suất O(N)
    for (const n of nums) {
        count.set(n, (count.get(n) || 0) + 1);
    }

    // 2. Phân loại vào bucket O(N)
    for (const [num, freq] of count) {
        bucket[freq].push(num);
    }

    // 3. Duyệt ngược từ tần suất cao nhất O(N)
    const res: number[] = [];
    for (let i = bucket.length - 1; i >= 0; i--) {
        if (bucket[i].length > 0) {
            for (const n of bucket[i]) {
                res.push(n);
                if (res.length === k) return res;
            }
        }
    }
    return res;
}

• Time Complexity: $O(N)$ - Bucket sort là tuyến tính.
• Space Complexity: $O(N)$ - Để lưu Map và Bucket array.

Pattern Nhận Diện

Khi cần Sort nhưng giá trị cần Sort nằm trong một khoảng số nguyên giới hạn (ở đây tần suất luôn $\le N$), hãy nghĩ đến Bucket Sort để đạt được độ phức tạp $O(N)$ thay vì $O(N \log N)$.

Ứng Dụng Thực Tế

Ví dụ: Xây dựng Tag Cloud (các tag phổ biến nhất), Suggestion System (các sản phẩm được mua nhiều nhất). Những hệ thống này thường cần top K items và cần tính toán cực nhanh trên dữ liệu lớn.