在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

• 对于初始化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