C++ में k सॉर्टेड सरणियों में m-वां सबसे छोटा मान ढूंढें

इस समस्या में, हमें अलग-अलग आकार की k विभिन्न सरणियां दी गई हैं। हमारा कार्य k सॉर्टेड सरणियों में m-वां सबसे छोटा मान ढूंढना है।

समस्या विवरण: यहां, हमें सभी k सरणियों के मर्ज की गई सरणी का m-वां सबसे छोटा तत्व ढूंढना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट: m = 4

arr[][] = { {4 , 7},

                                    {2, 5, 6},

                                    {3, 9, 12, 15, 19}}

आउटपुट: 5

व्याख्या:

मर्ज की गई सॉर्टेड सरणी: 2, 3, 4, 5, 6, 7, 9, 12, 15, 19

चौथा तत्व 5 है।

समाधान दृष्टिकोण:

m-वें सबसे छोटे तत्व को खोजने का एक सरल समाधान एक मर्ज की गई सरणी बनाना और फिर सरणी को आरोही क्रम में सॉर्ट करना है जिसमें सरणी का m-वां सबसे छोटा तत्व सूचकांक (m-1) पर होगा। इस आउटपुट मान को वापस करें।

एक अधिक प्रभावी समाधान मिन हीप डेटा संरचना का उपयोग करना होगा।

इसके लिए, हम एक मिन हीप बनाएंगे और सभी सरणियों से तत्व डालेंगे। और फिर m बार हीप से न्यूनतम तत्व को हटाएंगे और आउटपुट को सरणी में संग्रहीत करेंगे। फिर अगले तत्व को हीप में डालेंगे।

m-वें हटाए गए आइटम को प्रिंट करें।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,

उदाहरण

#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