在C ++中合并k个大小不同的排序数组
假设我们有不同的k个排序数组。我们必须合并这些数组并显示排序的结果。
因此，如果输入像k=3并且数组是{2，4}，{3,5,7}，{1，10，11，12}，那么输出将是123457101112
为了解决这个问题，我们将遵循以下步骤-
用第一个元素是整数，第二个元素是另一对整数来定义一种对，将其命名为ppi。
定义一个数组op
定义一个优先级队列q
对于初始化i：=0，当i<arr的大小时，更新（将i增加1），执行-
将（arr[i，0]，{i，0}）插入q
当q不为空时，-
将（arr[i，j+1]，{i，j+1}）插入q
current_element：=q的顶部元素
从q删除元素
i：=current_element中的第二个元素
j：=current_element中的第三个元素
在op的末尾插入current_element的第一个元素
如果j+1<arr[i]的大小，则＆minus
返回op
示例
让我们看下面的实现以更好地理解-
#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