इस समस्या में, हमें विभिन्न आकारों के k विभिन्न सरणियाँ दी गई हैं। हमारा काम k सॉर्ट किए गए सरणियों में m-th सबसे छोटा मान खोजना है।
समस्या का विवरण: यहां, हमें सभी k सरणियों के मर्ज किए गए सरणी के m-वें सबसे छोटे तत्व को खोजने की आवश्यकता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: मी =4
गिरफ्तारी [] [] ={ {4 , 7},
{2, 5, 6},
{3, 9, 12, 15, 19}}
आउटपुट: 5
स्पष्टीकरण:
मर्ज किए गए क्रमबद्ध सरणी :2, 3, 4, 5, 6, 7, 9, 12, 15, 19
चौथा तत्व 5 है।
समाधान दृष्टिकोण:
एम-वें सबसे छोटे तत्वों को खोजने का एक सरल उपाय एक मर्ज किए गए सरणी का निर्माण करना है और फिर सरणी को आरोही क्रम में क्रमबद्ध करना है जिसमें सूचकांक (एम -1) पर सरणी का एम-वें सबसे छोटा तत्व होगा। यह आउटपुट मान लौटाएं।
एक अधिक प्रभावी समाधान मिनी हीप . का उपयोग करना होगा डेटा संरचना।
ऐसा करने के लिए, हम एक न्यूनतम ढेर बनाएंगे और सभी सरणियों से तत्वों को सम्मिलित करेंगे। और फिर एम बार न्यूनतम तत्व तत्व को ढेर से हटा दें और आउटपुट को सरणी में संग्रहीत करें। फिर अगला तत्व हीप में डालें।
एम-वें हटाए गए आइटम को प्रिंट करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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