Pattern · Hash MapTrung bình
K Phần Tử Xuất Hiện Nhiều NhấtTop K Frequent Elements
Hiểu bài
Cho một mảng số nguyên nums và số nguyên k. Trả về k phần tử xuất hiện nhiều nhất trong mảng. Không cần sắp xếp kết quả theo thứ tự nào.
Ví dụ:
ts
nums = [1, 1, 1, 2, 2, 3], k = 2
output = [1, 2] // 1 xuất hiện 3 lần, 2 xuất hiện 2 lần
nums = [1], k = 1
output = [1]Đề bài đảm bảo đáp án là duy nhất — không có trường hợp hoà tần suất ở vị trí thứ k.
Ràng buộc: k ≤ số phần tử phân biệt trong mảng.
Cách cơ bản
O(n log n) time, O(n) spacets
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)
// Sắp xếp theo tần suất giảm dần → lấy k đầu
return [...freq.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(([val]) => val)
}Vì sao cách này chậm:
Bước sắp xếp toàn bộ Hash Map mất O(n log n).
Với k nhỏ, đây là lãng phí — ta chỉ cần k phần tử đứng đầu, không cần toàn bộ thứ tự.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.