Top K Frequent Elements — tìm K phần tử xuất hiện nhiều nhất. Vì sao bucket sort nhanh hơn heap ở đây?

Ý tưởng: Đếm tần suất bằng HashMap. Hai cách lấy top-K:
- Min-heap kích thước K: duyệt các tần suất, giữ heap K phần tử lớn nhất → O(n log K).
- Bucket sort: tần suất tối đa là n, nên tạo mảng buckets[freq] rồi quét từ cao xuống thấp lấy đủ K → O(n).

Vì sao bucket nhanh hơn: chỉ số bucket bị chặn bởi n (tần suất không thể vượt số phần tử), nên ta "sắp xếp" tần suất bằng đếm phân phối, bỏ được hệ số log.

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>()
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1)
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => [])
  for (const [num, f] of freq) buckets[f].push(num)
  const res: number[] = []
  for (let f = buckets.length - 1; f >= 0 && res.length < k; f--)
    for (const num of buckets[f]) { res.push(num); if (res.length === k) break }
  return res
}

Độ phức tạp: bucket O(n) thời gian & O(n) bộ nhớ.

Lưu ý: Heap vẫn là lựa chọn tốt khi K rất nhỏ so với n hoặc dữ liệu streaming; bucket sort cần biết trước giới hạn tần suất.