สมมติว่าเรามี k sorted arrays ต่างกัน เราต้องรวมอาร์เรย์เหล่านี้และแสดงผลการเรียงลำดับ
ดังนั้น หากอินพุตเป็น 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 เมื่อฉัน <ขนาดของ arr ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
- แทรก (arr[i, 0], {i, 0} ) ลงใน q
- ในขณะที่ q ไม่ว่างเปล่า ให้ทำ −
- current_element :=องค์ประกอบด้านบนของ q
- ลบองค์ประกอบออกจาก q
- i :=องค์ประกอบที่สองจาก current_element
- j :=องค์ประกอบที่สามจาก current_element
- แทรกองค์ประกอบแรกของ current_element ที่ส่วนท้ายของ op
- ถ้า j + 1 <ขนาดของ arr[i] แล้ว &ลบ
- แทรก (arr[i, j+1], {i, j+1} ) ลงใน q
- รีเทิร์น 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
