C++ में विभिन्न आकारों के k सॉर्ट किए गए सरणियों को मर्ज करें

मान लीजिए कि हमारे पास अलग-अलग k सॉर्ट किए गए सरणियाँ हैं। हमें इन सरणियों को मर्ज करना होगा और क्रमबद्ध परिणाम प्रदर्शित करना होगा।

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक प्रकार के युग्म को परिभाषित करें जिसमें पहला तत्व पूर्णांक है और दूसरा तत्व पूर्णांकों का दूसरा युग्म है, इसे ppi नाम दें।
• एक सरणी सेशन परिभाषित करें
• एक प्राथमिकता कतार q परिभाषित करें
• इनिशियलाइज़ i :=0 के लिए, जब i
• q में डालें (arr[i, 0], {i, 0} )

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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