समस्या विवरण
मान लीजिए हमारे पास विभिन्न 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