Combinar dos arrays ordenadas – Part 1

Posted on by Rudeus Greyrat
 

Dadas dos arrays ordenadas, la tarea es fusionarlas de manera ordenada.
Ejemplos: 

Entrada : arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8} 
Salida : arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
Entrada : arr1[] = { 5, 8, 9}, arr2[] = {4, 7, 8} 
Salida : arr3[] = {4, 5, 7, 8, 8, 9} 

 

Método 1 (O(n1 * n2) Tiempo y O(n1+n2) Espacio Extra) 

  1. Cree una array arr3[] de tamaño n1 + n2.
  2. Copie todos los elementos n1 de arr1[] a arr3[]
  3. Atraviese arr2[] e inserte elementos uno por uno (como ordenar por inserción ) de arr3[] a arr1[]. Este paso toma O(n1 * n2) tiempo.

Hemos discutido la implementación del método anterior en Merge two sorted arrays with O(1) extra space
Method 2 (O(n1 + n2) Time and O(n1 + n2) Extra Space) 
La idea es usar la función Merge de Merge sort . 

  1. Cree una array arr3[] de tamaño n1 + n2.
  2. Atraviese simultáneamente arr1[] y arr2[]. 
    • Elija los elementos actuales más pequeños en arr1[] y arr2[], copie este elemento más pequeño a la siguiente posición en arr3[] y avance en arr3[] y la array cuyo elemento se selecciona.
  3. Si quedan elementos en arr1[] o arr2[], cópielos también en arr3[].

La imagen de abajo es una ejecución en seco del enfoque anterior: 

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to merge two sorted arrays/
#include<iostream>
using namespace std;
  
// Merge arr1[0..n1-1] and arr2[0..n2-1] into
// arr3[0..n1+n2-1]
void mergeArrays(int arr1[], int arr2[], int n1,
                             int n2, int arr3[])
{
    int i = 0, j = 0, k = 0;
  
    // Traverse both array
    while (i<n1 && j <n2)
    {
        // Check if current element of first
        // array is smaller than current element
        // of second array. If yes, store first
        // array element and increment first array
        // index. Otherwise do same with second array
        if (arr1[i] < arr2[j])
            arr3[k++] = arr1[i++];
        else
            arr3[k++] = arr2[j++];
    }
  
    // Store remaining elements of first array
    while (i < n1)
        arr3[k++] = arr1[i++];
  
    // Store remaining elements of second array
    while (j < n2)
        arr3[k++] = arr2[j++];
}
  
// Driver code
int main()
{
    int arr1[] = {1, 3, 5, 7};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
  
    int arr2[] = {2, 4, 6, 8};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
  
    int arr3[n1+n2];
    mergeArrays(arr1, arr2, n1, n2, arr3);
  
    cout << "Array after merging" <<endl;
    for (int i=0; i < n1+n2; i++)
        cout << arr3[i] << " ";
  
    return 0;
}

Java

// Java program to merge two sorted arrays
import java.util.*;
import java.lang.*;
import java.io.*;
  
class MergeTwoSorted
{
    // Merge arr1[0..n1-1] and arr2[0..n2-1] 
    // into arr3[0..n1+n2-1]
    public static void mergeArrays(int[] arr1, int[] arr2, int n1,
                                int n2, int[] arr3)
    {
        int i = 0, j = 0, k = 0;
      
        // Traverse both array
        while (i<n1 && j <n2)
        {
            // Check if current element of first
            // array is smaller than current element
            // of second array. If yes, store first
            // array element and increment first array
            // index. Otherwise do same with second array
            if (arr1[i] < arr2[j])
                arr3[k++] = arr1[i++];
            else
                arr3[k++] = arr2[j++];
        }
      
        // Store remaining elements of first array
        while (i < n1)
            arr3[k++] = arr1[i++];
      
        // Store remaining elements of second array
        while (j < n2)
            arr3[k++] = arr2[j++];
    }
      
    public static void main (String[] args) 
    {
        int[] arr1 = {1, 3, 5, 7};
        int n1 = arr1.length;
      
        int[] arr2 = {2, 4, 6, 8};
        int n2 = arr2.length;
      
        int[] arr3 = new int[n1+n2];
          
        mergeArrays(arr1, arr2, n1, n2, arr3);
      
        System.out.println("Array after merging");
        for (int i=0; i < n1+n2; i++)
            System.out.print(arr3[i] + " ");
    }
}
  
/* This code is contributed by Mr. Somesh Awasthi */

Python 3

# Python program to merge
# two sorted arrays
  
# Merge arr1[0..n1-1] and 
# arr2[0..n2-1] into 
# arr3[0..n1+n2-1]
def mergeArrays(arr1, arr2, n1, n2):
    arr3 = [None] * (n1 + n2)
    i = 0
    j = 0
    k = 0
  
    # Traverse both array
    while i < n1 and j < n2:
      
        # Check if current element 
        # of first array is smaller 
        # than current element of 
        # second array. If yes, 
        # store first array element 
        # and increment first array
        # index. Otherwise do same 
        # with second array
        if arr1[i] < arr2[j]:
            arr3[k] = arr1[i]
            k = k + 1
            i = i + 1
        else:
            arr3[k] = arr2[j]
            k = k + 1
            j = j + 1
      
  
    # Store remaining elements
    # of first array
    while i < n1:
        arr3[k] = arr1[i];
        k = k + 1
        i = i + 1
  
    # Store remaining elements 
    # of second array
    while j < n2:
        arr3[k] = arr2[j];
        k = k + 1
        j = j + 1
    print("Array after merging")
    for i in range(n1 + n2):
        print(str(arr3[i]), end = " ")
  
# Driver code
arr1 = [1, 3, 5, 7]
n1 = len(arr1)
  
arr2 = [2, 4, 6, 8]
n2 = len(arr2)
mergeArrays(arr1, arr2, n1, n2);
  
# This code is contributed
# by ChitraNayal

C#

// C# program to merge
// two sorted arrays
using System;
  
class GFG
{
    // Merge arr1[0..n1-1] and 
    // arr2[0..n2-1] into 
    // arr3[0..n1+n2-1]
    public static void mergeArrays(int[] arr1, int[] arr2, 
                                   int n1, int n2, int[] arr3)
    {
        int i = 0, j = 0, k = 0;
      
        // Traverse both array
        while (i < n1 && j < n2)
        {
            // Check if current element 
            // of first array is smaller
            // than current element
            // of second array. If yes, 
            // store first array element 
            // and increment first array
            // index. Otherwise do same 
            // with second array
            if (arr1[i] < arr2[j])
                arr3[k++] = arr1[i++];
            else
                arr3[k++] = arr2[j++];
        }
      
        // Store remaining 
        // elements of first array
        while (i < n1)
            arr3[k++] = arr1[i++];
      
        // Store remaining elements
        // of second array
        while (j < n2)
            arr3[k++] = arr2[j++];
    }
      
    // Driver code
    public static void Main() 
    {
        int[] arr1 = {1, 3, 5, 7};
        int n1 = arr1.Length;
      
        int[] arr2 = {2, 4, 6, 8};
        int n2 = arr2.Length;
      
        int[] arr3 = new int[n1+n2];
      
        mergeArrays(arr1, arr2, n1, n2, arr3);
      
        Console.Write("Array after merging\n");
        for (int i = 0; i < n1 + n2; i++)
            Console.Write(arr3[i] + " ");
    }
}
  
// This code is contributed
// by ChitraNayal

PHP

<?php 
// PHP program to merge
// two sorted arrays
  
// Merge $arr1[0..$n1-1] and 
//       $arr2[0..$n2-1] into
//       $arr3[0..$n1+$n2-1]
function mergeArrays(&$arr1, &$arr2, 
                      $n1, $n2, &$arr3)
{
    $i = 0;
    $j = 0;
    $k = 0;
  
    // Traverse both array
    while ($i < $n1 && $j < $n2)
    {
        // Check if current element 
        // of first array is smaller 
        // than current element of 
        // second array. If yes, 
        // store first array element 
        // and increment first array
        // index. Otherwise do same
        // with second array
        if ($arr1[$i] < $arr2[$j])
            $arr3[$k++] = $arr1[$i++];
        else
            $arr3[$k++] = $arr2[$j++];
    }
  
    // Store remaining elements 
    // of first array
    while ($i < $n1)
        $arr3[$k++] = $arr1[$i++];
  
    // Store remaining elements
    // of second array
    while ($j < $n2)
        $arr3[$k++] = $arr2[$j++];
}
  
// Driver code
$arr1 = array(1, 3, 5, 7);
$n1 = sizeof($arr1);
  
$arr2 = array(2, 4, 6, 8);
$n2 = sizeof($arr2);
  
$arr3[$n1 + $n2] = array();
mergeArrays($arr1, $arr2, $n1, 
                   $n2, $arr3);
  
echo "Array after merging \n" ;
for ($i = 0; $i < $n1 + $n2; $i++)
    echo $arr3[$i] . " ";
  
// This code is contributed
// by ChitraNayal
?>

JavaScript

<script>
// javascript program to merge two sorted arrays
  
    // Merge arr1[0..n1-1] and arr2[0..n2-1]
    // into arr3[0..n1+n2-1]
    function mergeArrays(arr1,  arr2 , n1 , n2,  arr3) {
        var i = 0, j = 0, k = 0;
  
        // Traverse both array
        while (i < n1 && j < n2) {
            // Check if current element of first
            // array is smaller than current element
            // of second array. If yes, store first
            // array element and increment first array
            // index. Otherwise do same with second array
            if (arr1[i] < arr2[j])
                arr3[k++] = arr1[i++];
            else
                arr3[k++] = arr2[j++];
        }
  
        // Store remaining elements of first array
        while (i < n1)
            arr3[k++] = arr1[i++];
  
        // Store remaining elements of second array
        while (j < n2)
            arr3[k++] = arr2[j++];
    }
  
      
        var arr1 = [ 1, 3, 5, 7 ];
        var n1 = arr1.length;
  
        var arr2 = [ 2, 4, 6, 8 ];
        var n2 = arr2.length;
  
        var arr3 = Array(n1 + n2).fill(0);
  
        mergeArrays(arr1, arr2, n1, n2, arr3);
  
        document.write("Array after merging<br/>");
        for (i = 0; i < n1 + n2; i++)
            document.write(arr3[i] + " ");
  
// This code contributed by Rajput-Ji
</script>

Complete Interview Preparation - GFG

Producción: 

Array after merging
1 2 3 4 5 6 7 8

Complejidad de tiempo: O(n1 + n2) 
Espacio auxiliar: O(n1 + n2)
Método 3: Uso de mapas (O(nlog(n) + mlog(m)) Tiempo y O(N) Espacio extra) 

  1. Inserte elementos de ambas arrays en un mapa como claves.
  2. Imprime las claves del mapa.

A continuación se muestra la implementación del enfoque anterior. 

CPP

// C++ program to merge two sorted arrays 
//using maps 
#include<bits/stdc++.h>
using namespace std;
  
// Function to merge arrays
void mergeArrays(int a[], int b[], int n, int m) 
{
    // Declaring a map.
    // using map as a inbuilt tool
    // to store elements in sorted order.
    map<int, bool> mp;
      
    // Inserting values to a map.
    for(int i = 0; i < n; i++)
    mp[a[i]] = true;
      
    for(int i = 0;i < m;i++)
    mp[b[i]] = true;
      
    // Printing keys of the map.
    for(auto i: mp)
    cout<< i.first <<" ";
}
  
// Driver Code
int main()
{ 
    int a[] = {1, 3, 5, 7}, b[] = {2, 4, 6, 8};
      
    int size = sizeof(a)/sizeof(int);
    int size1 = sizeof(b)/sizeof(int);
      
    // Function call
    mergeArrays(a, b, size, size1);
      
    return 0;
}
  
//This code is contributed by yashbeersingh42

Java

// Java program to merge two sorted arrays 
//using maps 
import java.io.*;
import java.util.*;
  
class GFG {
      
    // Function to merge arrays
    static void mergeArrays(int a[], int b[], int n, int m) 
    {
        
        // Declaring a map.
        // using map as a inbuilt tool
        // to store elements in sorted order.
        Map<Integer,Boolean> mp = new TreeMap<Integer,Boolean>();
        
        // Inserting values to a map.
        for(int i = 0; i < n; i++)
        {
            mp.put(a[i], true);
        }
        for(int i = 0;i < m;i++)
        {
            mp.put(b[i], true);
        }
        
        // Printing keys of the map.
        for (Map.Entry<Integer,Boolean> me : mp.entrySet())
        {
            System.out.print(me.getKey() + " ");
        }
    }
      
    // Driver Code
    public static void main (String[] args) 
    {
        int a[] = {1, 3, 5, 7}, b[] = {2, 4, 6, 8};
        int size = a.length;
        int size1 = b.length;
          
        // Function call
        mergeArrays(a, b, size, size1);
    }
}
  
// This code is contributed by rag2127

Python3

# Python program to merge two sorted arrays
# using maps
import bisect
  
# Function to merge arrays
def mergeArrays(a, b, n, m):
    # Declaring a map.
    # using map as a inbuilt tool
    # to store elements in sorted order.
    mp=[]
      
    # Inserting values to a map.
    for i in range(n):
        bisect.insort(mp, a[i])
          
    for i in range(m):
        bisect.insort(mp, b[i])
      
    # Printing keys of the map.
    for i in mp:
        print(i,end=' ')
          
# Driver code
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
size = len(arr1)
size1 = len(arr2)
  
# Function call
mergeArrays(arr1, arr2, size, size1)
  
# This code is contributed by Pushpesh Raj

C#

// C# program to merge two sorted arrays 
//using maps 
using System;
using System.Collections.Generic;
  
public class GFG {
  
  // Function to merge arrays
  static void mergeArrays(int []a, int []b, int n, int m) 
  {
  
    // Declaring a map.
    // using map as a inbuilt tool
    // to store elements in sorted order.
    SortedDictionary<int, Boolean> mp = new SortedDictionary<int, Boolean>();
  
    // Inserting values to a map.
    for (int i = 0; i < n; i++) {
      mp.Add(a[i], true);
    }
    for (int i = 0; i < m; i++) {
      mp.Add(b[i], true);
    }
  
    // Printing keys of the map.
    foreach (KeyValuePair<int, Boolean> me in mp) {
      Console.Write(me.Key + " ");
    }
  }
  
  // Driver Code
  public static void Main(String[] args) {
    int []a = { 1, 3, 5, 7 };
    int []b = { 2, 4, 6, 8 };
    int size = a.Length;
    int size1 = b.Length;
  
    // Function call
    mergeArrays(a, b, size, size1);
  }
}
  
// This code is contributed by gauravrajput1

JavaScript

<script>
// javascript program to merge two sorted arrays 
//using maps     
  
    // Function to merge arrays
    function mergeArrays(a , b , n , m) 
    {
  
        // Declaring a map.
        // using map as a inbuilt tool
        // to store elements in sorted order.
        var mp = new Map();
  
        // Inserting values to a map.
        for (i = 0; i < n; i++) {
            mp.set(a[i], true);
        }
        for (i = 0; i < m; i++) {
            mp.set(b[i], true);
        }
        var a = [];
          
        // Printing keys of the map.
        for ( me of mp.keys()) {
            a.push(me);
        }
        a.sort();
        for ( me of a) {
            document.write(me + " ");
        }
    }
  
    // Driver Code
        var a = [ 1, 3, 5, 7 ], b = [ 2, 4, 6, 8 ];
        var size = a.length;
        var size1 = b.length;
  
        // Function call
        mergeArrays(a, b, size, size1);
  
// This code is contributed by gauravrajput1 
</script>

Producción:

1 2 3 4 5 6 7 8

Complejidad de tiempo: O( nlog(n) + mlog(m) ) 
Espacio auxiliar: O(N)
Brocade , Goldman-Sachs , Juniper , Linkedin , Microsoft , Quikr , Snapdeal , Synopsys , Zoho
Artículos relacionados : 
Combinar dos arreglos ordenados con O (1) espacio adicional  
Fusionar k arrays ordenadas | Conjunto 1
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.orgo envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

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

Deja una respuesta

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