Combinar 3 arrays ordenadas

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *