[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 […]
Nguồn: https://codegym.vn/blog/moi-ngay-1-thuat-toan-tim-phan-tu-thu-k-lon-nhat-trong-mang/