এই সমস্যায়, আমাদেরকে বিভিন্ন আকারের k বিভিন্ন অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল k সাজানো অ্যারেতে m-th ক্ষুদ্রতম মান খুঁজে বের করা।
সমস্যা বর্ণনা: এখানে, আমাদের সকল k অ্যারের মার্জড অ্যারের m-th ক্ষুদ্রতম উপাদান খুঁজে বের করতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: m =4
arr[][] ={ {4 , 7},
{2, 5, 6},
{3, 9, 12, 15, 19}}
আউটপুট: ৫
ব্যাখ্যা:
মার্জ করা সাজানো অ্যারে :2, 3, 4, 5, 6, 7, 9, 12, 15, 19
৪র্থ উপাদান হল ৫.
সমাধান পদ্ধতি:
m-th ক্ষুদ্রতম উপাদানগুলি খুঁজে বের করার একটি সহজ সমাধান হল একটি মার্জড অ্যারে তৈরি করা এবং তারপর অ্যারেটিকে ক্রমবর্ধমান ক্রমে সাজান যাতে সূচকে অ্যারের m-th ক্ষুদ্রতম উপাদান থাকবে (m-1)। এই আউটপুট মান ফেরত দিন।
আরও কার্যকর সমাধান হল মিনিট হিপ ব্যবহার করা ডেটা স্ট্রাকচার।
এর জন্য, আমরা একটি মিন হিপ তৈরি করব এবং সমস্ত অ্যারে থেকে উপাদান সন্নিবেশ করব। এবং তারপর m বার স্তূপ থেকে মিন এলিমেন্ট অপসারণ করুন এবং অ্যারেতে আউটপুট সংরক্ষণ করুন। তারপর পরবর্তী উপাদানটি হিপে প্রবেশ করান।
m-th অপসারণ আইটেম মুদ্রণ.
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, pair<int, int> > ppi;
int findMSmallestElement(vector<vector<int> > sortedArr, int m) {
priority_queue<ppi, vector<ppi>, greater<ppi> > priorQueue;
for (int i = 0; i < sortedArr.size(); i++)
priorQueue.push({ sortedArr[i][0], { i, 0 } });
int count = 0;
int i = 0, j = 0;
while (count < m && priorQueue.empty() == false) {
ppi curr = priorQueue.top();
priorQueue.pop();
i = curr.second.first;
j = curr.second.second;
if (j + 1 < sortedArr[i].size())
priorQueue.push( { sortedArr[i][j + 1], { i, (j + 1) } });
count++;
}
return sortedArr[i][j];
}
int main() {
vector<vector<int> > arr{ {4 , 7},
{2, 5, 6},
{3, 9, 12, 15, 19}};
int m = 6;
cout<<m<<"th smallest value in k sorted arrays is "<<findMSmallestElement(arr, m);
return 0;
} আউটপুট
6th smallest value in k sorted arrays is 7
