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.
Java
import java.util.*;
// Java program to merge three sorted arrays
// by merging two at a time.
class GFG {
static ArrayList<Integer> mergeTwo(List<Integer> A,
List<Integer> B)
{
// Get sizes of vectors
int m = A.size();
int n = B.size();
// ArrayList for storing Result
ArrayList<Integer> D = new ArrayList<Integer>(m + n);
int i = 0, j = 0;
while (i < m && j < n) {
if (A.get(i) <= B.get(j))
D.add(A.get(i++));
else
D.add(B.get(j++));
}
// B has exhausted
while (i < m)
D.add(A.get(i++));
// A has exhausted
while (j < n)
D.add(B.get(j++));
return D;
}
// Driver code
public static void main(String[] args)
{
Integer[] a = { 1, 2, 3, 5 };
Integer[] b = { 6, 7, 8, 9 };
Integer[] c = { 10, 11, 12 };
List<Integer> A = Arrays.asList(a);
List<Integer> B = Arrays.asList(b);
List<Integer> C = Arrays.asList(c);
// First Merge A and B
ArrayList<Integer> T = mergeTwo(A, B);
// Print Result after merging T with C
System.out.println(mergeTwo(T, C));
}
}
/* This code contributed by PrinciRaj1992 */
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:
Java
import java.util.*;
import java.io.*;
import java.lang.*;
class Sorting {
public static void main(String[] args)
{
int A[] = { 1, 2, 41, 52, 84 };
int B[] = { 1, 2, 41, 52, 67 };
int C[] = { 1, 2, 41, 52, 67, 85 };
// call the function to sort and print the sorted numbers
merge3sorted(A, B, C);
}
// Function to merge three sorted arrays
// A[], B[], C[]: input arrays
static void merge3sorted(int A[], int B[], int C[])
{
// creating an empty list to store sorted numbers
ArrayList<Integer> list = new ArrayList<Integer>();
int i = 0, j = 0, k = 0;
// using merge concept and trying to find
// smallest of three while all three arrays
// contains at least one element
while (i < A.length && j < B.length && k < C.length) {
int a = A[i];
int b = B[j];
int c = C[k];
if (a <= b && a <= c) {
list.add(a);
i++;
}
else if (b <= a && b <= c) {
list.add(b);
j++;
}
else {
list.add(c);
k++;
}
}
// next three while loop is to sort two
// of arrays if one of the three gets exhausted
while (i < A.length && j < B.length) {
if (A[i] < B[j]) {
list.add(A[i]);
i++;
}
else {
list.add(B[j]);
j++;
}
}
while (j < B.length && k < C.length) {
if (B[j] < C[k]) {
list.add(B[j]);
j++;
}
else {
list.add(C[k]);
k++;
}
}
while (i < A.length && k < C.length) {
if (A[i] < C[k]) {
list.add(A[i]);
i++;
}
else {
list.add(C[k]);
k++;
}
}
// if one of the array are left then
// simply appending them as there will
// be only largest element left
while (i < A.length) {
list.add(A[i]);
i++;
}
while (j < B.length) {
list.add(B[j]);
j++;
}
while (k < C.length) {
list.add(C[k]);
k++;
}
// finally print the list
for (Integer x : list)
System.out.print(x + " ");
} // merge3sorted closing braces
}
[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 .
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