Dadas 3 arrays (A, B, C) que están ordenadas en orden ascendente, debemos fusionarlas en orden ascendente y generar la array D.
Ejemplos:
Input : A = [1, 2, 3, 4, 5]
B = [2, 3, 4]
C = [4, 5, 6, 7]
Output : D = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]
Input : A = [1, 2, 3, 5]
B = [6, 7, 8, 9 ]
C = [10, 11, 12]
Output: D = [1, 2, 3, 5, 6, 7, 8, 9. 10, 11, 12]
Método 1 (dos arreglos a la vez)
Hemos discutido en Combinar 2 arreglos ordenados . Entonces, primero podemos fusionar dos arrays y luego fusionar la resultante con la tercera array. Complejidad de tiempo para fusionar dos arrays O (m + n). Entonces, para fusionar la tercera array, la complejidad del tiempo se convertirá en O (m + n + o). Tenga en cuenta que esta es de hecho la mejor complejidad de tiempo que se puede lograr para este problema.
Complejidad espacial : dado que fusionamos dos arrays a la vez, necesitamos otra array para almacenar el resultado de la primera fusión. Esto eleva la complejidad del espacio a O(m+n). Tenga en cuenta que el espacio requerido para contener el resultado de 3 arrays se ignora al calcular la complejidad.
Algoritmo
function merge(A, B)
Let m and n be the sizes of A and B
Let D be the array to store result
// Merge by taking smaller element from A and B
while i < m and j < n
if A[i] <= B[j]
Add A[i] to D and increment i by 1
else Add B[j] to D and increment j by 1
// If array A has exhausted, put elements from B
while j < n
Add B[j] to D and increment j by 1
// If array B has exhausted, put elements from A
while i < n
Add A[j] to D and increment i by 1
Return D
function merge_three(A, B, C)
T = merge(A, B)
return merge(T, C)
Las implementaciones se dan a continuación.
C++
// C++ program to merge three sorted arrays
// by merging two at a time.
#include <iostream>
#include <vector>
using namespace std;
using Vector = vector<int>;
void printVector(const Vector& a)
{
cout << "[";
for (auto e : a)
cout << e << " ";
cout << "]" << endl;
}
Vector mergeTwo(Vector& A, Vector& B)
{
// Get sizes of vectors
int m = A.size();
int n = B.size();
// Vector for storing Result
Vector D;
D.reserve(m + n);
int i = 0, j = 0;
while (i < m && j < n) {
if (A[i] <= B[j])
D.push_back(A[i++]);
else
D.push_back(B[j++]);
}
// B has exhausted
while (i < m)
D.push_back(A[i++]);
// A has exhausted
while (j < n)
D.push_back(B[j++]);
return D;
}
// Driver Code
int main()
{
Vector A = { 1, 2, 3, 5 };
Vector B = { 6, 7, 8, 9 };
Vector C = { 10, 11, 12 };
// First Merge A and B
Vector T = mergeTwo(A, B);
// Print Result after merging T with C
printVector(mergeTwo(T, C));
return 0;
}
Producción:
[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
Método 2 (Tres arreglos a la vez)
La complejidad espacial del método 1 se puede mejorar fusionando los tres arreglos.
function merge-three(A, B, C)
Let m, n, o be size of A, B, and C
Let D be the array to store the result
// Merge three arrays at the same time
while i < m and j < n and k < o
Get minimum of A[i], B[j], C[i]
if the minimum is from A, add it to
D and advance i
else if the minimum is from B add it
to D and advance j
else if the minimum is from C add it
to D and advance k
// After above step at least 1 array has
// exhausted. Only C has exhausted
while i < m and j < n
put minimum of A[i] and B[j] into D
Advance i if minimum is from A else advance j
// Only B has exhausted
while i < m and k < o
Put minimum of A[i] and C[k] into D
Advance i if minimum is from A else advance k
// Only A has exhausted
while j < n and k < o
Put minimum of B[j] and C[k] into D
Advance j if minimum is from B else advance k
// After above steps at least 2 arrays have
// exhausted
if A and B have exhausted take elements from C
if B and C have exhausted take elements from A
if A and C have exhausted take elements from B
return D
Complejidad: La complejidad del tiempo es O(m+n+o) ya que procesamos cada elemento de las tres arrays una vez. Solo necesitamos una array para almacenar el resultado de la fusión y, por lo tanto, ignorando esta array, la complejidad del espacio es O (1).
La implementación del algoritmo se da a continuación:
C++
// C++ program to merger three sorted arrays
// by merging three simultaneously.
#include <iostream>
#include <vector>
using namespace std;
using Vector = vector<int>;
void printVector(const Vector& a)
{
cout << "[";
for (auto e : a) {
cout << e << " ";
}
cout << "]" << endl;
}
Vector mergeThree(Vector& A, Vector& B,
Vector& C)
{
int m, n, o, i, j, k;
// Get Sizes of three vectors
m = A.size();
n = B.size();
o = C.size();
// Vector for storing output
Vector D;
D.reserve(m + n + o);
i = j = k = 0;
while (i < m && j < n && k < o) {
// Get minimum of a, b, c
int m = min(min(A[i], B[j]), C[k]);
// Put m in D
D.push_back(m);
// Increment i, j, k
if (m == A[i])
i++;
else if (m == B[j])
j++;
else
k++;
}
// C has exhausted
while (i < m && j < n) {
if (A[i] <= B[j]) {
D.push_back(A[i]);
i++;
}
else {
D.push_back(B[j]);
j++;
}
}
// B has exhausted
while (i < m && k < o) {
if (A[i] <= C[k]) {
D.push_back(A[i]);
i++;
}
else {
D.push_back(C[k]);
k++;
}
}
// A has exhausted
while (j < n && k < o) {
if (B[j] <= C[k]) {
D.push_back(B[j]);
j++;
}
else {
D.push_back(C[k]);
k++;
}
}
// A and B have exhausted
while (k < o)
D.push_back(C[k++]);
// B and C have exhausted
while (i < m)
D.push_back(A[i++]);
// A and C have exhausted
while (j < n)
D.push_back(B[j++]);
return D;
}
// Driver Code
int main()
{
Vector A = { 1, 2, 41, 52, 84 };
Vector B = { 1, 2, 41, 52, 67 };
Vector C = { 1, 2, 41, 52, 67, 85 };
// Print Result
printVector(mergeThree(A, B, C));
return 0;
}
[1 1 1 2 2 2 41 41 41 52 52 52 67 67 84 85 ]
Nota: si bien es relativamente fácil implementar procedimientos directos para fusionar dos o tres arrays, el proceso se vuelve engorroso si queremos fusionar 4 o más arrays. En tales casos, debemos seguir el procedimiento que se muestra en Merge K Sorted Arrays .
Otro enfoque (sin preocuparse por la array agotadora):
el código escrito anteriormente se puede acortar con el código siguiente. Aquí no necesitamos escribir código si alguna array se agota.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to merge three sorted arrays
// Without caring about the exhausting array
#include <bits/stdc++.h>
using namespace std;
// A[], B[], C[]: input arrays
// Function to merge three sorted lists into a single
// list.
vector<int> merge3sorted(vector<int>& A, vector<int>& B,
vector<int>& C)
{
vector<int> ans;
int l1 = A.size();
int l2 = B.size();
int l3 = C.size();
int i = 0, j = 0, k = 0;
while (i < l1 || j < l2 || k < l3) {
// Assigning a, b, c with max values so that if
// any value is not present then also we can sort
// the array.
int a = INT_MAX, b = INT_MAX, c = INT_MAX;
// a, b, c variables are assigned only if the
// value exist in the array.
if (i < l1)
a = A[i];
if (j < l2)
b = B[j];
if (k < l3)
c = C[k];
// Checking if 'a' is the minimum
if (a <= b && a <= c) {
ans.push_back(a);
i++;
}
// Checking if 'b' is the minimum
else if (b <= a && b <= c) {
ans.push_back(b);
j++;
}
// Checking if 'c' is the minimum
else {
if (c <= a && c <= b) {
ans.push_back(c);
k++;
}
}
}
return ans;
}
// A utility function to print array list
void printeSorted(vector<int> list)
{
for (auto x : list)
cout << x << " ";
}
// Driver program to test above functions
int main()
{
vector<int> A = { 1, 2, 41, 52, 84 };
vector<int> B = { 1, 2, 41, 52, 67 };
vector<int> C = { 1, 2, 41, 52, 67, 85 };
vector<int> final_ans = merge3sorted(A, B, C);
printeSorted(final_ans);
return 0;
}
// This code is contributed by Pushpesh raj
1 1 1 2 2 2 41 41 41 52 52 52 67 67 84 85
Complejidad de tiempo: O(m+n+o) donde m, n, o son las longitudes de las arrays 1, 2 y 3.
Consulte el artículo completo sobre Merge 3 Sorted Arrays para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA