Pattern · Heap (Hàng đợi ưu tiên)Trung bình
Phần Tử Lớn Thứ K Trong MảngKth Largest Element in an Array
Hiểu bài
Cho mảng nums và số nguyên k. Trả về phần tử lớn thứ k trong mảng (tính theo thứ tự sắp xếp, KHÔNG phải phần tử phân biệt thứ k — giá trị trùng vẫn đếm riêng từng vị trí).
Ví dụ:
ts
nums = [3, 2, 1, 5, 6, 4], k = 2
output = 5 // sắp giảm dần: 6, 5, 4, 3, 2, 1 → thứ 2 là 5
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
output = 4 // sắp giảm dần: 6, 5, 5, 4, ... → thứ 4 là 4Câu hỏi kèm theo kinh điển: "làm được mà KHÔNG sort toàn bộ mảng không?" — đó là lúc heap xuất hiện.
Cách cơ bản
O(n log n) time, O(n) spacets
function findKthLargest(nums: number[], k: number): number {
const sorted = [...nums].sort((a, b) => b - a) // sắp xếp giảm dần
return sorted[k - 1]
}Vì sao cách này chậm:
Sort toàn bộ mảng chỉ để lấy 1 vị trí — làm thừa việc khi k nhỏ hơn n nhiều (ví dụ tìm top 10 trong 1 triệu phần tử).
Interviewer thường chấp nhận đây là bước mở đầu rồi yêu cầu tối ưu.
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.