Hợp nhất k mảng được sắp xếp có kích thước khác nhau trong C ++

Giả sử chúng ta có k mảng được sắp xếp khác nhau. Chúng tôi phải hợp nhất các mảng này và hiển thị kết quả đã sắp xếp.

Vì vậy, nếu đầu vào là k =3 và các mảng là {2, 4}, {3, 5, 7}, {1, 10, 11, 12}, thì đầu ra sẽ là 1 2 3 4 5 7 10 11 12

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• xác định một loại cặp với phần tử đầu tiên là một số nguyên và phần tử thứ hai là một cặp số nguyên khác, đặt tên là ppi.
• Xác định op mảng
• xác định một hàng đợi ưu tiên q
• để khởi tạo i:=0, khi tôi
• insert (arr [i, 0], {i, 0}) vào q

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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] << " ";
}

Đầu vào

{{ 2,4}, { 3,5,7 }, { 1, 10, 11, 12 }}

Đầu ra

1 2 3 4 5 7 10 11 12