Dadas 3 arrays (A, B, C) que están ordenadas en orden ascendente, debemos fusionarlas en orden ascendente y generar la array D.
Ejemplos:
Entrada: A = [1, 2, 3, 4, 5]
B = [2, 3, 4]
C = [4, 5, 6, 7]
Salida: D = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]Entrada: A = [1, 2, 3, 5]
B = [6, 7, 8, 9]
C = [10, 11, 12]
Salida: 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.
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)
A continuación se muestra la implementación del enfoque anterior:
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;
}
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 */
Python
# Python program to merge three sorted arrays # by merging two at a time. def merge_two(a, b): (m, n) = (len(a), len(b)) i = j = 0 # Destination Array d = [] # Merge from a and b together while i < m and j < n: if a[i] <= b[j]: d.append(a[i]) i += 1 else: d.append(b[j]) j += 1 # Merge from a if b has run out while i < m: d.append(a[i]) i += 1 # Merge from b if a has run out while j < n: d.append(b[j]) j += 1 return d def merge(a, b, c): t = merge_two(a, b) return merge_two(t, c) if __name__ == "__main__": A = [1, 2, 3, 5] B = [6, 7, 8, 9] C = [10, 11, 12] print(merge(A, B, C))
C#
// C# program to merge three sorted arrays
// by merging two at a time.
using System;
using System.Collections.Generic;
public static class GFG {
static void printVector(List<int> a)
{
Console.Write("[");
foreach(var e in a)
{
Console.Write(e);
Console.Write(" ");
}
Console.Write("]");
Console.Write("\n");
}
static List<int> mergeTwo(List<int> A, List<int> B)
{
// Get sizes of vectors
int m = A.Count;
int n = B.Count;
// Vector for storing Result
List<int> D = new List<int>();
D.Capacity = m + n;
int i = 0;
int j = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
D.Add(A[i++]);
}
else {
D.Add(B[j++]);
}
}
// B has exhausted
while (i < m) {
D.Add(A[i++]);
}
// A has exhausted
while (j < n) {
D.Add(B[j++]);
}
return D;
}
// Driver Code
public static void Main()
{
List<int> A = new List<int>() { 1, 2, 3, 5 };
List<int> B = new List<int>() { 6, 7, 8, 9 };
List<int> C = new List<int>() { 10, 11, 12 };
// First Merge A and B
List<int> T = mergeTwo(A, B);
// Print Result after merging T with C
printVector(mergeTwo(T, C));
}
}
// This code is contributed by Aarti_Rathi
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 ]
Complejidad de tiempo: O(m+n+o) donde m, n, o son las longitudes de la 1.ª, 2.ª y 3.ª array.
Espacio Auxiliar: O(m + n + o).
Método 2 (Tres arreglos a la vez)
La complejidad espacial del método 1 se puede mejorar si fusionamos 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 de tiempo: O(m+n+o) donde m, n, o son las longitudes de la primera, segunda y tercera array.
Espacio Auxiliar: O(1).
A continuación se muestra la implementación del enfoque anterior:
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;
}
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
}
Python
# Python program to merge three sorted arrays # simultaneously. def merge_three(a, b, c): (m, n, o) = (len(a), len(b), len(c)) i = j = k = 0 # Destination array d = [] while i < m and j < n and k < o: # Get Minimum element m = min(a[i], b[j], c[k]) # Add m to D d.append(m) # Increment the source pointer which # gives m if a[i] == m: i += 1 elif b[j] == m: j += 1 elif c[k] == m: k += 1 # Merge a and b in c has exhausted while i < m and j < n: if a[i] <= b[k]: d.append(a[i]) i += 1 else: d.append(b[j]) j += 1 # Merge b and c if a has exhausted while j < n and k < o: if b[j] <= c[k]: d.append(b[j]) j += 1 else: d.append(c[k]) k += 1 # Merge a and c if b has exhausted while i < m and k < o: if a[i] <= c[k]: d.append(a[i]) i += 1 else: d.append(c[k]) k += 1 # Take elements from a if b and c # have exhausted while i < m: d.append(a[i]) i += 1 # Take elements from b if a and c # have exhausted while j < n: d.append(b[j]) j += 1 # Take elements from c if a and # b have exhausted while k < o: d.append(c[k]) k += 1 return d if __name__ == "__main__": a = [1, 2, 41, 52, 84] b = [1, 2, 41, 52, 67] c = [1, 2, 41, 52, 67, 85] print(merge_three(a, b, c))
C#
// Online C# Editor for free
// Write, Edit and Run your C# code using C# Online Compiler
using System;
using System.Collections;
class Sorting
{
// 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 list = new ArrayList();
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++;
}
Console.Write("[ ");
// finally print the list
for (int x=0;x<list.Count;x++)
Console.Write(list[x]+" ");
Console.Write("]");
} // merge3sorted closing braces
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);
}
}
// This code is contributed by Aarti_Rathi
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>
Producción
[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 la primera, segunda y tercera array.
Espacio Auxiliar: O(m+n+o).
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
// by merging two at a time.
#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
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.lang.*;
import java.util.*;
// Java program to merge three sorted arrays
// by merging two at a time.
// This code is contributed by Animesh Nag
class Solution {
// A[], B[], C[]: input arrays
// Function to merge three sorted lists into a single
// list.
static ArrayList<Integer> merge3sorted(int A[], int B[],
int C[])
{
ArrayList<Integer> ans = new ArrayList<Integer>();
int l1 = A.length;
int l2 = B.length;
int l3 = C.length;
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 = Integer.MAX_VALUE,
b = Integer.MAX_VALUE,
c = Integer.MAX_VALUE;
// 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.add(a);
i++;
}
// Checking if 'b' is the minimum
else if (b <= a && b <= c) {
ans.add(b);
j++;
}
// Checking if 'c' is the minimum
else {
if (c <= a && c <= b) {
ans.add(c);
k++;
}
}
}
return ans;
}
}
class GFG {
// Driver program to test above functions
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 };
Solution sol = new Solution();
ArrayList<Integer> final_ans
= sol.merge3sorted(A, B, C);
printeSorted(final_ans);
}
// A utility function to print array list
static void printeSorted(ArrayList<Integer> list)
{
for (Integer x : list)
System.out.print(x + " ");
}
}
Python
# Python program to merge three sorted arrays # simultaneously. def merge3sorted(A, B, C): (l1, l2, l3) = (len(A), len(B), len(C)) i = j = k = 0 # Destination array ans = [] while (i < l1 or j < l2 or k < l3): # Assigning a, b, c with max values so that if # any value is not present then also we can sort # the array a = 9999 b = 9999 c = 9999 # 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 and a <= c): ans.append(a) i += 1 # Checking if 'b' is the minimum elif (b <= a and b <= c): ans.append(b) j += 1 # Checking if 'c' is the minimum elif (c <= a and c <= b): ans.append(c) k += 1 return ans if __name__ == "__main__": A = [1, 2, 41, 52, 84] B = [1, 2, 41, 52, 67] C = [1, 2, 41, 52, 67, 85] print(merge3sorted(A, B, C)) # This code is contributed by Aarti_Rathi
C#
using System;
using System.Collections.Generic;
public static class GFG {
// C# program to merge three sorted arrays
// by merging two at a time.
// A[], B[], C[]: input arrays
// Function to merge three sorted lists into a single
// list.
public static List<int>
merge3sorted(List<int> A, List<int> B, List<int> C)
{
List<int> ans = new List<int>();
int l1 = A.Count;
int l2 = B.Count;
int l3 = C.Count;
int i = 0;
int j = 0;
int 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.MaxValue;
int b = int.MaxValue;
int c = int.MaxValue;
// 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.Add(a);
i++;
}
// Checking if 'b' is the minimum
else if (b <= a && b <= c) {
ans.Add(b);
j++;
}
// Checking if 'c' is the minimum
else {
if (c <= a && c <= b) {
ans.Add(c);
k++;
}
}
}
return new List<int>(ans);
}
// A utility function to print array list
public static void printeSorted(List<int> list)
{
foreach(var x in list)
{
Console.Write(x);
Console.Write(" ");
}
}
// Driver program to test above functions
public static void Main()
{
List<int> A = new List<int>() { 1, 2, 41, 52, 84 };
List<int> B = new List<int>() { 1, 2, 41, 52, 67 };
List<int> C
= new List<int>() { 1, 2, 41, 52, 67, 85 };
List<int> final_ans = merge3sorted(A, B, C);
printeSorted(new List<int>(final_ans));
}
}
// This code is contributed by Aarti_Rathi
Javascript
// javascript program to merge three sorted arrays
// by merging two at a time.
// A[], B[], C[]: input arrays
// Function to merge three sorted lists into a single
// list.
function merge3sorted(A, B, C)
{
var ans = new Array();
var l1 = A.length;
var l2 = B.length;
var l3 = C.length;
var i = 0;
var j = 0;
var 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.
var a = Number.MAX_VALUE;
var b = Number.MAX_VALUE;
var c = Number.MAX_VALUE;
// 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) > 0);
i++;
}
else if (b <= a && b <= c)
{
(ans.push(b) > 0);
j++;
}
else
{
if (c <= a && c <= b)
{
(ans.push(c) > 0);
k++;
}
}
}
return ans;
}
// A utility function to print array list
function printeSorted(list)
{
console.log("[ ");
for ( const x of list) {console.log(x + " ");}
console.log(" ]");
}
// Driver program to test above functions
var A = [1, 2, 41, 52, 84];
var B = [1, 2, 41, 52, 67];
var C = [1, 2, 41, 52, 67, 85];
var final_ans = merge3sorted(A, B, C);
printeSorted(final_ans);
// This code is contributed by Aarti_Rathi
Producción
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 la primera, segunda y tercera array.
Complejidad espacial : O(m+n+o)
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA