Thuật toán: Tìm số lớn thứ K (không dùng Sort)¶
🟠 Quan trọng · Thuật toán
Cách 1: Min-Heap (Priority Queue)¶
Ý tưởng: Duy trì heap có đúng K phần tử. Phần tử nhỏ nhất = số lớn thứ K.
- Thêm K phần tử đầu tiên vào min-heap
- Với mỗi phần tử còn lại: nếu > đỉnh heap → thay thế đỉnh, heapify
- Cuối cùng, đỉnh heap = số lớn thứ K
Độ phức tạp: O(N log K). Rất hiệu quả khi K nhỏ.
Cách 2: QuickSelect¶
Ý tưởng: Chọn pivot, partition. Nếu pivot ở đúng vị trí K → xong. Không → đệ quy 1 bên.
- Chọn pivot ngẫu nhiên
- Partition: lớn hơn pivot sang trái, nhỏ hơn sang phải
- Nếu vị trí pivot = K-1 → trả về
- Nếu không → đệ quy vào bên chứa vị trí K
Độ phức tạp: Trung bình O(N), xấu nhất O(N²).
So sánh¶
| Thuật toán | Time (avg) | Time (worst) | Space |
|---|---|---|---|
| Min-Heap | O(N log K) | O(N log K) | O(K) |
| QuickSelect | O(N) | O(N²) | O(1) |