এই টিউটোরিয়ালে, আমরা k-th খুঁজে বের করতে যাচ্ছি প্রতিটি সন্নিবেশের পর ক্ষুদ্রতম উপাদান।
আমরা সমস্যা সমাধানের জন্য মিন-হিপ ব্যবহার করতে যাচ্ছি। চলুন প্রোগ্রামটি সম্পূর্ণ করার ধাপগুলো দেখি।
- এলোমেলো ডেটা দিয়ে অ্যারে শুরু করুন।
- অগ্রাধিকার সারি শুরু করুন।
- k - 1 পর্যন্ত কোনো k-th থাকবে না ক্ষুদ্রতম উপাদান। সুতরাং, আপনার পছন্দের যেকোনো চিহ্ন প্রিন্ট করুন।
- একটি লুপ লিখুন যা k + 1 থেকে n পর্যন্ত পুনরাবৃত্তি করে।
- মিন-হিপের রুট প্রিন্ট করুন।
- যদি উপাদানটি মিন-হিপের মূলের চেয়ে বড় হয়, তাহলে রুটটি পপ করুন এবং উপাদানটি প্রবেশ করান৷
উদাহরণ
আসুন কোডটি দেখি।
#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;
} আউটপুট
আপনি যদি উপরের কোডটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
- - - - 2 3 3 3 5 5
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
