Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में विभिन्न आकारों के k क्रमबद्ध सरणियों को मर्ज करें

समस्या विवरण

मान लीजिए हमारे पास विभिन्न k क्रमबद्ध सरणियां हैं। हमें इन सरणियों को मर्ज करना है और क्रमबद्ध परिणाम प्रदर्शित करना है।

उदाहरण

यदि इनपुट k = 3 और सरणियां हैं {2, 4}, {3, 5, 7}, {1, 10, 11, 12}, तो आउटपुट 1 2 3 4 5 7 10 11 12 होगा।

एल्गोरिदम चरण

  • एक जोड़ी प्रकार परिभाषित करें जिसका पहला तत्व एक पूर्णांक है और दूसरा तत्व पूर्णांकों की एक और जोड़ी है, इसे ppi नाम दें।
  • एक सरणी op परिभाषित करें
  • एक प्राथमिकता कतार q परिभाषित करें
  • प्रत्येक सरणी के लिए, पहला तत्व q में डालें
  • जब तक q खाली नहीं है:
    • current_element := q का शीर्ष तत्व
    • q से तत्व हटाएं
    • i := current_element से दूसरा तत्व
    • j := current_element से तीसरा तत्व
    • current_element के पहले तत्व को op के अंत में डालें
    • यदि j + 1 < arr[i] का आकार, तो (arr[i][j+1], {i, j+1}) को q में डालें
  • op वापस करें

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

#define ppi pair<int,pair<int,int>>

vector<int> merge(vector<vector<int> > arr){
    vector<int> op;
    priority_queue<ppi, vector<ppi>, greater<ppi> > queue;
    for (int i = 0; i < arr.size(); i++)
        queue.push({ arr[i][0], { i, 0 } });
    while (queue.empty() == false) {
        ppi current_element = queue.top();
        queue.pop();
        int i = current_element.second.first;
        int j = current_element.second.second;
        op.push_back(current_element.first);
        if (j + 1 < arr[i].size())
            queue.push({ arr[i][j + 1], { i, j + 1 } });
    }
    return op;
}

int main(){
    vector<vector<int> > arr{ { 2,4}, { 3,5,7 }, { 1, 10, 11, 12 } };
    vector<int> output = merge(arr);
    for(int i = 0; i<output.size(); i++)
        cout << output[i] << " ";
}

इनपुट

{{ 2,4}, { 3,5,7 }, { 1, 10, 11, 12 }}

आउटपुट

1 2 3 4 5 7 10 11 12
  1. C/C++ में मल्टीडायमेंशनल ऐरे C/C++ में मल्टीडायमेंशनल ऐरे

    C/C++ में, मल्टीडायमेंशनल ऐरे को सरल शब्दों में ऐरे के ऐरे के रूप में परिभाषित किया जाता है। मल्टीडायमेंशनल ऐरे में डेटा टेबुलर फॉर्म में स्टोर होता है (रो मेजर ऑर्डर में)। निम्नलिखित डायग्राम 3 x 3 x 3 डायमेंशन वाले मल्टीडायमेंशनल ऐरे के लिए मेमोरी आवंटन रणनीति दिखाता है। एल्गोरिदम Begin ऐर

  1. - C++ में सरणी (Arrays) का उपयोग कैसे करें?

    एक सरणी एक ही प्रकार के तत्वों की एक श्रृंखला है जो सन्निहित मेमोरी स्थानों में रखी जाती है जिन्हें एक यूनिक आइडेंटिफायर में इंडेक्स जोड़कर व्यक्तिगत रूप से संदर्भित किया जा सकता है। C++ में सरणी का उपयोग करने के लिए, आपको पहले इसे घोषित करना होगा, उदाहरण के लिए, int arr[10]; यह आकार 10 की int प्रका

  1. - जावा में K क्रमबद्ध सरणियों को मर्ज करें

    हमें n संख्या में सरणियाँ दी गई हैं, मान लें कि हम तीन सरणियाँ लेते हैं यानी arr1[], arr2[] और arr3[] पूर्णांक प्रकार की। कार्य सभी दी गई पूर्णांक सरणियों को इस तरह मर्ज करना है कि परिणामी सरणी केवल रनटाइम में क्रमबद्ध हो।आइए उदाहरण से समझते हैंइनपुट -Inta[]={21,22,23,24};int b[ ] ={28,31,35}आउटपुट