C++ এ বিভিন্ন আকারের k সাজানো অ্যারে মার্জ করুন

ধরুন আমাদের বিভিন্ন k সাজানো অ্যারে আছে। আমাদের এই অ্যারেগুলিকে একত্রিত করতে হবে এবং সাজানো ফলাফল প্রদর্শন করতে হবে৷

সুতরাং, যদি ইনপুট হয় k =3 এবং অ্যারেগুলি হয় {2, 4},{3, 5, 7},{1, 10, 11, 12}, তাহলে আউটপুট হবে 1 2 3 4 5 7 10 11 12

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• প্রথম উপাদানটি একটি পূর্ণসংখ্যা এবং দ্বিতীয় উপাদানটি আরেকটি পূর্ণসংখ্যার সাথে এক ধরনের জোড়া সংজ্ঞায়িত করুন, এটিকে পিপিআই নাম দিন৷
• একটি অ্যারে op সংজ্ঞায়িত করুন
• একটি অগ্রাধিকার কিউ সংজ্ঞায়িত করুন 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