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

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

bởi ngoctran2 | 17:31 | Blog | Thuật toán

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++

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

4. Mã nguồn Java

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

5. Mã nguồn Python

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

Xem thêm các bài viết thú vị về Thuật toán tại đây!

 

0 Lời bình

Gửi Lời bình

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

BÀI VIẾT LIÊN QUAN

BẠN MUỐN HỌC LẬP TRÌNH?

GỌI NGAY

098 953 44 58

Đăng ký tư vấn lộ trình học lập trình

Đăng ký tư vấn, định hướng lộ trình học và giải đáp các thắc mắc về ngành nghề – Miễn phí – Online.

2 + 3 =

TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM
TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM