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.
Javascript
<script>
// Javascript program to merge three sorted arrays
// by merging two at a time.
function mergeTwo(A, B)
{
// Get sizes of vectors
let m = A.length;
let n = B.length;
// Vector for storing Result
let D = [];
let i = 0, j = 0;
while (i < m && j < n) {
if (A[i] <= B[j])
D.push(A[i++]);
else
D.push(B[j++]);
}
// B has exhausted
while (i < m)
D.push(A[i++]);
// A has exhausted
while (j < n)
D.push(B[j++]);
return D;
}
// Driver Code
let A = [ 1, 2, 3, 5 ];
let B = [ 6, 7, 8, 9 ];
let C = [ 10, 11, 12 ];
// First Merge A and B
let T = mergeTwo(A, B);
// Print Result after merging T with C
document.write(mergeTwo(T, C));
</script>
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:
Javascript
<script>
// Javascript program to merger three sorted arrays
// by merging three simultaneously.
function printVector(a) {
document.write("[");
for (let e of a) {
document.write(e + " ");
}
document.write("]" + "<br>");
}
function mergeThree(A, B, C)
{
let m, n, o, i, j, k;
// Get Sizes of three vectors
m = A.length;
n = B.length;
o = C.length;
// Vector for storing output
let D = [];
i = j = k = 0;
while (i < m && j < n && k < o)
{
// Get minimum of a, b, c
let m = Math.min(Math.min(A[i], B[j]), C[k]);
// Put m in D
D.push(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(A[i]);
i++;
}
else {
D.push(B[j]);
j++;
}
}
// B has exhausted
while (i < m && k < o) {
if (A[i] <= C[k]) {
D.push(A[i]);
i++;
}
else {
D.push(C[k]);
k++;
}
}
// A has exhausted
while (j < n && k < o) {
if (B[j] <= C[k]) {
D.push(B[j]);
j++;
}
else {
D.push(C[k]);
k++;
}
}
// A and B have exhausted
while (k < o)
D.push(C[k++]);
// B and C have exhausted
while (i < m)
D.push(A[i++]);
// A and C have exhausted
while (j < n)
D.push(B[j++]);
return D;
}
// Driver Code
let A = [1, 2, 41, 52, 84];
let B = [1, 2, 41, 52, 67];
let C = [1, 2, 41, 52, 67, 85];
// Print Result
printVector(mergeThree(A, B, C));
// This code is contributed by gfgking.
</script>
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:
Javascript
<script>
// Javascript program to merger three sorted arrays
// Without caring about the exhausting array
function printVector(a) {
document.write("[");
for (let e of a) {
document.write(e + " ");
}
document.write("]" + "<br>");
}
// A[], B[], C[]: input arrays
// Function to merge three sorted lists into a single
// list.
function merge3sorted(A, B, C)
{
let ans = [];
// Get Sizes of three vectors
let l1 = A.length;
let l2 = B.length;
let l3 = C.length;
let i = 0;
let j = 0;
let 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.
let a = Number.MAX_SAFE_INTEGER;
let b = Number.MAX_SAFE_INTEGER;
let c = Number.MAX_SAFE_INTEGER;
// 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(a);
i++;
}
// Checking if 'b' is the minimum
if (b <= a && b <= c) {
ans.push(b);
j++;
}
// Checking if 'c' is the minimum
if (c <= a && c <= b) {
ans.push(c);
k++;
}
}
return ans;
}
// Driver Code
let A = [1, 2, 41, 52, 84];
let B = [1, 2, 41, 52, 67];
let C = [1, 2, 41, 52, 67, 85];
let final_ans = merge3sorted(A, B, C);
// Print Result
printVector(final_ans);
// This code is contributed by Pushpesh Raj
</script>
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