C++で異なるサイズのk個のソートされた配列をマージします

異なるk個のソートされた配列があるとします。これらの配列をマージして、ソートされた結果を表示する必要があります。

したがって、入力がk =3のようで、配列が{2、4}、{3、5、7}、{1、10、11、12}の場合、出力は1 2 3 4 5 71011になります。 12

これを解決するには、次の手順に従います-

• 最初の要素が整数で、2番目の要素が別の整数のペアであるペアの1つのタイプを定義し、ppiという名前を付けます。
• 配列操作を定義する
• 1つの優先キューを定義するq
• iを初期化する場合：=0、i
• （arr [i、0]、{i、0}）をqに挿入

例

理解を深めるために、次の実装を見てみましょう-

#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