Kth Largest Element in an Array
- Nhãn: Mảng, Chia để trị, Sắp xếp nhanh, Sắp xếp, Heap (Hàng đợi ưu tiên)
- Độ khó: Trung bình
Ý tưởng
Mô tả: Cho một mảng số nguyên chưa được sắp xếp và một số nguyên .
Yêu cầu: Trả về phần tử lớn thứ trong mảng.
Giải thích:
- Yêu cầu sử dụng thuật toán với độ phức tạp thời gian .
- .
- .
Ví dụ:
- Ví dụ 1:
- Ví dụ 2:
Ý tưởng giải quyết
Đây là một bài toán rất tốt, thường được đặt trong phỏng vấn.
Ý tưởng đầu tiên mà ta có thể nghĩ đến là: sắp xếp mảng và trả về phần tử thứ . Vấn đề chính ở đây là độ phức tạp của phương pháp sắp xếp.
Phương pháp sắp xếp nổi bọt, sắp xếp chọn, sắp xếp chèn có độ phức tạp thời gian quá cao và dễ dẫn đến việc vượt quá thời gian chạy.
Có thể xem xét Heap Sort, sắp xếp trộn, sắp xếp nhanh.
Yêu cầu của bài toán là tìm phần tử lớn thứ , sắp xếp trộn chỉ có thể trả về phần tử thứ sau khi hoàn tất sắp xếp. Trong khi Heap Sort, sau mỗi lần sắp xếp, một phần tử sẽ được xác định chính xác vị trí của nó, tương tự như sắp xếp nhanh.
Ý tưởng 1: Heap Sort
Ý tưởng của Heap Sort tăng dần như sau:
- Xây dựng một max heap (heap ban đầu), đảm bảo giá trị lớn nhất trong giá trị của mảng nằm ở vị trí đầu tiên.
- Điều chỉnh heap: Hoán đổi vị trí giữa phần tử đầu tiên của dãy phần tử (phần tử lớn nhất) và phần tử thứ của dãy. Xây dựng một max heap từ phần tử đầu tiên của dãy, đảm bảo giá trị lớn nhất trong giá trị của mảng nằm ở vị trí đầu tiên, từ đó thu được phần tử lớn thứ hai.
- Điều chỉnh heap: Hoán đổi vị trí giữa phần tử đầu tiên của dãy phần tử (phần tử lớn thứ hai) và phần tử thứ của dãy. Xây dựng một max heap từ phần tử đầu tiên của dãy, đảm bảo giá trị lớn nhất trong giá trị của mảng nằm ở vị trí đầu tiên, từ đó thu được phần tử lớn thứ ba.
- Tiếp tục như vậy, liên tục hoán đổi vị trí giữa phần tử đầu tiên của dãy phần tử và phần tử thứ của dãy. Xây dựng một max heap từ phần tử đầu tiên của dãy, đảm bảo giá trị lớn nhất trong giá trị của mảng nằm ở vị trí đầu tiên, từ đó thu được phần tử lớn thứ .
Ý tưởng 1: Mã giả
Ý tưởng 1: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 2: Sắp xếp nhanh
Sử dụng sắp xếp nhanh, mỗi lần điều chỉnh, một phần tử sẽ được xác định chính xác vị trí của nó và mảng được chia thành hai mảng con bên trái và bên phải, các phần tử trong mảng con bên trái đều nhỏ hơn phần tử đó, các phần tử trong mảng con bên phải đều lớn hơn phần tử đó.
Vì vậy, chỉ cần phần tử chia lần này là phần tử thứ thì tìm được kết quả. Và chúng ta chỉ cần quan tâm đến trạng thái sắp xếp của mảng con chứa phần tử lớn thứ , các phần tử không liên quan đến phần tử lớn thứ có thể bỏ qua. Điều này giúp giảm số bước thực hiện.
Ý tưởng 2: Mã giả
Ý tưởng 2: Phân tích độ phức tạp
- Độ phức tạp thời gian: . Quá trình này được chứng minh trong “Giáo trình thuật toán 9.2: Thuật toán chọn có kỳ vọng tuyến tính”.
- Độ phức tạp không gian: . Chi phí không gian dự phòng của đệ quy là .
Ý tưởng 3: Sử dụng thư viện chuẩn (không khuyến nghị)
Đoạn mã nhanh nhất trong đệ trình là gọi phương thức sort
của Python. Phương pháp này thích hợp để tiết kiệm thời gian khi tham gia cuộc thi lập trình, nhưng bạn có thể thử viết mã của riêng mình trong quá trình luyện tập hàng ngày.
Ý tưởng 3: Mã giả
Ý tưởng 3: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .
Ý tưởng 4: Hàng đợi ưu tiên
- Duyệt qua các phần tử trong mảng, đối với mỗi phần tử :
- Nếu số lượng phần tử trong hàng đợi ưu tiên nhỏ hơn , thì đưa phần tử hiện tại vào hàng đợi ưu tiên.
- Nếu số lượng phần tử trong hàng đợi ưu tiên lớn hơn hoặc bằng , và phần tử hiện tại lớn hơn phần tử đầu hàng đợi ưu tiên, thì loại bỏ phần tử đầu hàng đợi ưu tiên và đưa phần tử hiện tại vào hàng đợi ưu tiên.
- Sau khi duyệt qua, phần tử đầu tiên trong hàng đợi ưu tiên chính là phần tử lớn thứ .
Trong đây, chúng ta sử dụng thư viện heapq
của Python để triển khai hàng đợi ưu tiên, bước này cũng có thể triển khai hàng đợi ưu tiên bằng cách viết lại cách triển khai của heap.
Ý tưởng 4: Mã giả
Ý tưởng 4: Phân tích độ phức tạp
- Độ phức tạp thời gian: .
- Độ phức tạp không gian: .