Trong hướng dẫn này, chúng ta sẽ tìm k-th phần tử nhỏ nhất sau mỗi lần chèn.
Chúng tôi sẽ sử dụng min-heap để giải quyết vấn đề. Hãy xem các bước để hoàn thành chương trình.
- Khởi tạo mảng với dữ liệu ngẫu nhiên.
- Khởi tạo hàng đợi ưu tiên.
- Cho đến k - 1 sẽ không có bất kỳ k-th nào phần tử nhỏ nhất. Vì vậy, hãy in bất kỳ ký hiệu nào bạn thích.
- Viết một vòng lặp lặp lại từ k + 1 đến n.
- In phần gốc của min-heap.
- Nếu phần tử lớn hơn phần tử gốc của min-heap, hãy mở phần tử gốc và chèn phần tử.
Ví dụ
Hãy xem mã.
#include <bits/stdc++.h> using namespace std; void findKthSmallestElement(int elements[], int n, int k) { priority_queue<int, vector<int>, greater<int>> queue; for (int i= 0; i < k - 1; i++) { queue.push(elements[i]); cout << "- "; } queue.push(elements[k-1]); for (int i = k; i < n; i++) { cout << queue.top() << " "; if (elements[i] > queue.top()) { queue.pop(); queue.push(elements[i]); } } cout << queue.top() << endl; } int main() { int arr[] = {3, 5, 6, 2, 7, 8, 2, 3, 5, 9}; findKthSmallestElement(arr, 10, 5); return 0; }
Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
- - - - 2 3 3 3 5 5
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.