Hàng đợi ưu tiên tìm Top-K phần tử bằng Heap

Mục tiêu kiến thức

• Sử dụng thư viện chuẩn heapq và collections.Counter trong Python.
• Tối ưu hóa bài toán Top-K phần tử xuất hiện nhiều nhất với độ phức tạp O(N log K).
• Xử lý quy tắc hòa điểm (Tie-breaking): nếu hai phần tử có cùng tần suất, phần tử có giá trị nhỏ hơn sẽ đứng trước.

Mô tả bài toán

Trong hệ thống tiền xử lý dữ liệu huấn luyện mô hình ngôn ngữ lớn (LLM Tokenizer) tại AI Empire Academy, ta cần xác định k token (mỗi token biểu diễn bằng một số nguyên) xuất hiện nhiều nhất trong một văn bản dài.

Cho danh sách số nguyên nums và một số nguyên dương k. Hãy viết hàm top_k_frequent(nums: list[int], k: int) -> list[int] trả về danh sách gồm k số nguyên có tần suất xuất hiện cao nhất.

Quy tắc sắp xếp kết quả:

• Sắp xếp theo tần suất xuất hiện giảm dần.
• Nếu hai số có cùng tần suất, số có giá trị nhỏ hơn sẽ đứng trước.
• Nếu k ≤ 0 hoặc k > số lượng phần tử phân biệt trong nums, hàm phải ném ra ngoại lệ ValueError("k khong hop le").

Ràng buộc

• 1 ≤ len(nums) ≤ 10⁵.
• -10⁹ ≤ nums[i] ≤ 10⁹.
• 1 ≤ k ≤ 10⁴.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.