Top K Frequent Elements: ba cách giải và khi nào dùng cái nào

Ba cách giải thực sự khác nhau tồn tại cho bài này, và cái nào bạn chọn nói lên bạn đã hiểu gì. Follow-up — "thuật toán của bạn phải tốt hơn O(n log n)" — loại bỏ cách tiếp cận hiển nhiên và buộc bạn chọn giữa heap và một cấu trúc mà phần lớn người chưa nghĩ tới.

Những gì constraint thực sự ép buộc

Bài toán: cho nums (tối đa 10^5 phần tử, giá trị trong [-10^4, 10^4]) và số nguyên k, trả về k phần tử xuất hiện nhiều nhất theo bất kỳ thứ tự nào.

Hai constraint quan trọng ở đây. Thứ nhất, k được đảm bảo nằm trong khoảng [1, số phần tử unique] — bạn không cần xử lý k bất khả thi, và đáp án được đảm bảo là duy nhất (không có hai phần tử nào có cùng tần số đúng tại ranh giới thứ k). Thứ hai, và thú vị hơn, follow-up nói độ phức tạp thời gian phải tốt hơn O(n log n).

Constraint thứ hai loại bỏ sorting hoàn toàn. Thứ thay thế nó phụ thuộc vào việc k nhỏ so với n hay bạn muốn linear time thực sự.

Còn một constraint ẩn đáng chú ý: giá trị phần tử bị giới hạn trong [-10^4, 10^4]. Điều đó không ảnh hưởng trực tiếp đến ba approach này, nhưng nó có nghĩa là tần số bị giới hạn bởi n, không phải bởi range của giá trị. Chính bound đó trên tần số là thứ làm bucket sort hoạt động.

Bước zero: đếm tần số

Cả ba approach đều bắt đầu như nhau. Xây dựng frequency map trong O(n).

from collections import Counter
freq = Counter(nums)   # {phần tử: số lần xuất hiện}

Trong C#:

var freq = new Dictionary<int, int>();
foreach (int n in nums)
    freq[n] = freq.GetValueOrDefault(n, 0) + 1;

Sau bước này, bài toán biến đổi: cho value -> frequency, trả về k entry có frequency cao nhất. Sự khác biệt giữa các approach nằm hoàn toàn ở cách trích xuất top-k entry đó.

Approach 1: sort frequency map — O(n log n)

Sort các phần tử unique theo frequency giảm dần, lấy k phần tử đầu. Đây là baseline bạn viết để xác nhận bạn hiểu bài.

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        freq = Counter(nums)
        return [x for x, _ in sorted(freq.items(), key=lambda p: p[1], reverse=True)[:k]]

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var freq = new Dictionary<int, int>();
        foreach (int n in nums)
            freq[n] = freq.GetValueOrDefault(n, 0) + 1;
 
        var sorted = freq.OrderByDescending(kvp => kvp.Value).Take(k);
        return sorted.Select(kvp => kvp.Key).ToArray();
    }
}

O(n log n) — đếm là O(n), sort các phần tử phân biệt nhiều nhất là O(n log n). Gọn, dễ đọc, và bị loại bởi follow-up.

Trace tay với nums = [1,1,1,2,2,3], k = 2:

Sau khi đếm:       freq = {1: 3, 2: 2, 3: 1}
Sort giảm dần:     [(1, 3), (2, 2), (3, 1)]
Lấy k=2 đầu tiên: [1, 2]

Tôi vẫn viết cách này trước trong phỏng vấn như baseline, rồi nói "follow-up loại cách này ra, để tôi làm tốt hơn."

Complexity: O(n log n) time, O(n) space. Không qua follow-up.

Approach 2: min-heap kích thước k — O(n log k)

Giữ một min-heap đúng k entry, sắp xếp theo frequency. Với mỗi entry mới từ frequency map, push vào heap, rồi pop nếu heap vượt quá k. Phần tử bị pop luôn là cái có frequency thấp nhất — nghĩa là sau khi xử lý hết, heap giữ đúng top-k.

import heapq
from collections import Counter
 
class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        freq = Counter(nums)
        # entry trong heap là (frequency, element) để heapq so sánh theo frequency trước
        heap: list[tuple[int, int]] = []
        for val, count in freq.items():
            heapq.heappush(heap, (count, val))
            if len(heap) > k:
                heapq.heappop(heap)   # đuổi phần tử frequency thấp nhất
        return [val for _, val in heap]

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var freq = new Dictionary<int, int>();
        foreach (int n in nums)
            freq[n] = freq.GetValueOrDefault(n, 0) + 1;
 
        // PriorityQueue<TElement, TPriority> là min-heap trong .NET 6+
        // priority thấp nhất (= frequency thấp nhất) dequeue trước
        var heap = new PriorityQueue<int, int>();
        foreach (var (val, count) in freq) {
            heap.Enqueue(val, count);
            if (heap.Count > k)
                heap.Dequeue();   // đuổi phần tử ít xuất hiện nhất
        }
 
        var result = new int[k];
        for (int i = 0; i < k; i++)
            result[i] = heap.Dequeue();
        return result;
    }
}

Trace tay với nums = [1,1,1,2,2,3], k = 2:

Entry trong heap có dạng (frequency, value). Min-heap giữ frequency nhỏ nhất ở root.

freq = {1: 3, 2: 2, 3: 1}

Xử lý val=1, count=3:
  push (3, 1)   -> heap: [(3,1)]        size=1, không evict

Xử lý val=2, count=2:
  push (2, 2)   -> heap: [(2,2), (3,1)] size=2, không evict
                          ^root (min-freq)

Xử lý val=3, count=1:
  push (1, 3)   -> heap: [(1,3), (3,1), (2,2)]  size=3 > k=2
  pop min (1,3) -> heap: [(2,2), (3,1)]          size=2
                          ^root

Kết quả: các phần tử từ heap = [2, 1]  (thứ tự bất kỳ đều hợp lệ)

Thứ tự push-trước-pop-sau là cố ý: phần tử mới cạnh tranh với đương kim yếu nhất trước khi bất cứ thứ gì bị loại. Nếu pop trước push, bạn có thể loại phần tử mới mà không cho nó cơ hội cạnh tranh.

Tại sao dùng min-heap để tìm top? Vì bạn muốn đuổi phần tử yếu nhất khi heap đầy. Phần tử nhỏ nhất nằm ở root của min-heap, làm eviction tốn O(log k). Với max-heap, phần tử yếu nhất bị chôn sâu ở leaf — bạn phải linear-scan để tìm nó.

Complexity: O(n log k) time — mỗi trong số tối đa n giá trị phân biệt đều trải qua một push và có thể một pop, cả hai là O(log k). O(n) space cho frequency map, O(k) cho heap. Vì k <= n, cách này chặt chẽ hơn O(n log n) bất cứ khi nào k < n.

Approach 3: bucket sort — O(n)

Cách này đòi hỏi nhận ra cấu trúc ẩn: frequency bị giới hạn bởi độ dài mảng. Một giá trị không thể xuất hiện quá n lần. Vậy thay vì sort theo frequency, bạn có thể index trực tiếp theo frequency.

Cấp phát n + 1 bucket. buckets[i] chứa tất cả giá trị xuất hiện đúng i lần. Rồi quét từ buckets[n] xuống buckets[1], thu thập giá trị cho đến khi đủ k. Tổng chi phí: O(n).

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        freq = Counter(nums)
        buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
        for val, count in freq.items():
            buckets[count].append(val)
 
        result: list[int] = []
        for i in range(len(buckets) - 1, 0, -1):
            for val in buckets[i]:
                result.append(val)
                if len(result) == k:
                    return result
        return result

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var freq = new Dictionary<int, int>();
        foreach (int n in nums)
            freq[n] = freq.GetValueOrDefault(n, 0) + 1;
 
        // buckets[i] = danh sách phần tử xuất hiện đúng i lần
        var buckets = new List<int>[nums.Length + 1];
        for (int i = 0; i <= nums.Length; i++)
            buckets[i] = new List<int>();
 
        foreach (var (val, count) in freq)
            buckets[count].Add(val);
 
        var result = new List<int>();
        for (int i = nums.Length; i >= 1 && result.Count < k; i--)
            result.AddRange(buckets[i]);
 
        return result.Take(k).ToArray();
    }
}

Trace tay với nums = [1,1,1,2,2,3], k = 2:

freq = {1: 3, 2: 2, 3: 1}   n = 6, cấp phát buckets[0..6]

Điền bucket:
  val=1, count=3  ->  buckets[3] = [1]
  val=2, count=2  ->  buckets[2] = [2]
  val=3, count=1  ->  buckets[1] = [3]

Quét từ i=6 xuống:
  i=6: []  (rỗng)
  i=5: []  (rỗng)
  i=4: []  (rỗng)
  i=3: [1]  ->  result=[1],  size=1 < k=2
  i=2: [2]  ->  result=[1,2], size=2 == k, return [1, 2]

Cấu trúc bucket làm cho việc quét hiệu quả:

Constraint làm cho cách này khả thi — frequency <= độ dài mảng — hiển nhiên khi đã nêu ra nhưng dễ bỏ qua dưới áp lực phỏng vấn. Chính nó cho phép pre-size mảng bucket mà không cần bất kỳ cấu trúc hash nào.

Complexity: O(n) time, O(n) space. Cả mảng bucket lẫn frequency map đều là O(n). Bạn không mất gì về space so với heap, và đạt được linear time bound.

So sánh độ phức tạp

Edge case và code xử lý thế nào

• k = 1: bạn chỉ muốn phần tử có frequency cao nhất. Heap không bao giờ giữ quá 1 entry, thoái hóa thành running maximum. Bucket sort dừng ở bucket không rỗng đầu tiên từ trên xuống.
• k = số phần tử unique: bạn muốn tất cả. Heap lấp đầy đến k và không bao giờ evict — mọi phần tử đều sống sót. Bucket sort thu thập hết trước khi dừng.
• nums = [1], k = 1: một phần tử duy nhất, frequency 1. Frequency map có một entry; cả ba approach trả về [1] ngay. Điều duy nhất cần kiểm tra là buckets[1] tồn tại khi n=1 — nó có, vì bạn cấp phát n+1 = 2 bucket.
• Tất cả phần tử phân biệt: nums = [1,2,3,4], k = 2. Mỗi phần tử có frequency 1. Bucket sort đổ mọi thứ vào buckets[1] và trả về k phần tử đầu tiên gặp — thứ tự không được chỉ định, bài toán chấp nhận điều đó. Heap giữ hai phần tử được xử lý cuối cùng, cũng không xác định thứ tự, cũng ổn.
• k lớn gần bằng n: nếu k = n - 1, heap giữ gần như mọi thứ và thoái hóa về gần O(n log n). Bucket sort vẫn O(n). Đây là nơi khoảng cách lý thuyết giữa hai approach thực sự xuất hiện trong thực tế.

Nên dùng cái nào

Sorting là cách bạn viết để xác nhận bạn hiểu bài. Heap là cái bạn viết khi cần chứng minh mình làm tốt hơn. Bucket sort là cái bạn viết khi muốn O(n) và có thể giải thích constraint đó ra ngoài miệng.

Trong thực tế tôi mặc định dùng heap. O(n log k), đúng, gọn, và dùng cấu trúc mà người phỏng vấn nhận ra ngay. Bucket sort là câu trả lời lý thuyết đẹp hơn, nhưng giải thích tại sao n + 1 bucket là đủ cần một câu người phỏng vấn phải nghe trước khi bạn viết code — không phải sau.

Khoảng cách O(n log k) vs O(n) quan trọng ở quy mô lớn. Ở n = 10^5 và k = 10^4, heap thực hiện khoảng 10^5 * 14 ~ 1.4M phép tính; bucket sort thực hiện đúng 10^5. Khác biệt thực sự. Ở n = 100 với bất kỳ k nào, không ai quan tâm. Để quy mô thực tế của bài toán quyết định cái nào dùng.

Bài này trong series arrays-hashing

Đây là bài đỉnh điểm của mạch frequency-counting trong series. Two Sums dùng seen-set cho membership O(1); Valid Anagram dùng frequency array cho character counting; Group Anagrams dùng canonical-key map. Ở đây, frequency tự nó trở thành dữ liệu first-class, và câu hỏi là làm thế nào để xếp hạng theo nó một cách hiệu quả.

Mental model nền — "khi các giá trị bị giới hạn, index theo giá trị thay vì sort" — xuất hiện lại trong radix sort, counting sort, và bất kỳ bài toán nào mà range của một key là O(n). Một khi bạn thấy nó ở đây, bạn sẽ nhận ra nó ở nơi khác.

Các bài anh em đáng làm tiếp theo:

• 215. Kth Largest Element in an Array — cùng pattern size-k heap, key theo value không phải frequency; giới thiệu quickselect như một lựa chọn O(n) thay thế
• 692. Top K Frequent Words — cùng frequency counting, thêm lexicographic tie-breaking làm phức tạp hóa phép so sánh trong heap
• 451. Sort Characters By Frequency — frequency bucket sort nhưng bạn trả về tất cả ký tự đã sort, không có giới hạn k
• 973. K Closest Points to Origin — heap key theo khoảng cách Euclidean; frequency map được thay bằng tính toán khoảng cách