Top K Frequent Elements: vì sao min-heap O(n log k) thắng sort



Top K Frequent Elements: sort toàn bộ tần suất tốn O(n log n), còn min-heap giữ đúng k phần tử chỉ tốn O(n log k). Đây là cách nhận ra bài heap trong vài giây khi phỏng vấn thuật toán.

▸ Bước 1: đếm tần suất bằng bảng băm (Dictionary), O(n)
▸ Sort cả danh sách tần suất là lãng phí: sắp xếp luôn những phần tử không bao giờ lọt top k
▸ Min-heap kích thước k: vượt k thì pop phần tử nhỏ nhất, còn O(n log k) thời gian và O(k) bộ nhớ thêm
▸ PriorityQueue trong .NET 6 trở lên mặc định là min-heap, dùng được ngay cho bài này
▸ Quy tắc nhận dạng: hỏi k lớn nhất thì dùng min-heap, hỏi k nhỏ nhất thì dùng max-heap

Đăng ký kênh để luyện mỗi ngày một câu phỏng vấn thuật toán hay gặp.

🌐 Website:
ⓕ Fan Page:
ⓕ FB:
📩 Liên hệ hợp tác: duylinh191@gmail.com

#Shorts #TopKFrequentElements #MinHeap #PhongVanIT #ThuatToan #LeetCode #Heap #PriorityQueue #CSharp #DotNet #CodingInterview #DSA

source

Leave a Reply

Your email address will not be published. Required fields are marked *

You might like

© 2026 Cantinho do Vídeo - WordPress Video Theme by WPEnjoy