[Mỗi ngày 1 thuật toán] Tìm phần tử thứ K lớn nhất trong mảng

Tiếp nỗi chuỗi series “Mỗi ngày 1 thuật toán” là bài toán Tìm phần tử thứ K lớn nhất trong mảng. Để giải bài toán này, CodeGym sẽ cung cấp cho bạn ba đoạn mã nguồn quan trọng, bao gồm: C++, Java, và Python. 

1. Ý tưởng chính của bài toán Tìm phần tử thứ K lớn nhất

Cho một mảng các số nguyên và một số nguyên k, hãy tìm phần tử đứng thứ k trong mảng về độ lớn.

Giải pháp sử dụng min-heap

• Tạo một min-heap chứa k phần tử lớn nhất trong mảng. Sau khi duyệt hết mảng, phần tử ở đỉnh heap chính là phần tử thứ k lớn nhất.
• Ưu điểm: Hiệu quả hơn với các giá trị k nhỏ so với sắp xếp toàn bộ mảng.
• Nhược điểm: Cần thêm không gian để lưu trữ heap.

Lưu ý

• Có thể sử dụng giải pháp khác, chẳng hạn như sắp xếp trước, như sẽ có ưu/nhược điểm nhất định về độ phức tạp.

2. Ví dụ minh hoạ của bài toán

• Ví dụ 1:
  • Cho mảng [3, 2, 1, 5, 6, 4], và số k = 2
  • Kết quả: 5 (Phần tử lớn thứ hai là 5)
• Ví dụ 2:
  • Cho mảng [3, 2, 3, 1, 2, 4, 5, 5, 6], và số k = 4
  • Kết quả: 4 (Phần tử lớn thứ tư là 4)

3. Mã nguồn C++

4. Mã nguồn Java

5. Mã nguồn Python