Top K Frequent Elements: min-heap O(n log k) thắng sort toàn mảng



Top K Frequent Elements là câu thuật toán phỏng vấn rất hay gặp: sort toàn bộ là O(n log n), còn min-heap kích thước k chỉ O(n log k). Short này cho bạn quy tắc nhận ra bài heap trong vài giây.

▸ Bước 1: đếm tần suất bằng hash map (Dictionary trong C#), O(n)
▸ Đẩy từng phần tử vào min-heap, heap vượt k thì pop phần tử nhỏ nhất, heap chỉ tốn O(k) bộ nhớ
▸ Vì sao O(n log k) thắng sort: không tốn công sắp xếp những phần tử không bao giờ lọt top k
▸ 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
▸ C# PriorityQueue mặc định là min-heap, và bucket sort O(n) là phương án nên nhắc thêm với interviewer

Subscribe để luyện mỗi ngày một câu phỏng vấn thuật toán ngắn gọn, đúng trọng tâm.

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

#Shorts #TopKFrequentElements #MinHeap #PhongVanIT #ThuatToan #Heap #PriorityQueue #LeetCode #CodingInterview #DataStructures #CSharp #BigO

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