Zwei sortierte Arrays zusammenführen
Bei zwei sortierten Arrays besteht die Aufgabe darin, sie sortiert zusammenzuführen.
Beispiele:
Eingabe : arr1[] = {1, 3, 4, 5}, arr2[] = {2, 4, 6, 8}
Ausgabe : arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
Eingabe : arr1[] = {5, 8, 9}, arr2[] = {4, 7, 8}
Ausgabe : arr3[] = {4, 5, 7, 8, 8, 9}
Methode 1 (O(n1 * n2) Zeit und O(n1+n2) Extra Space)
- Erstellen Sie ein Array arr3[] der Größe n1 + n2.
- Kopiere alle n1 Elemente von arr1[] nach arr3[]
- Durchlaufen Sie arr2[] und fügen Sie nacheinander Elemente (wie insert sort ) von arr3[] bis arr1[] ein. Dieser Schritt dauert O(n1 * n2) Zeit.
Wir haben die Implementierung der obigen Methode in Merge two sorted Arrays with O(1) extra space
Methode 2 (O(n1 + n2) Time and O(n1 + n2) Extra Space)
besprochen. Die Idee ist, die Merge-Funktion von Merge sort zu verwenden .
- Erstellen Sie ein Array arr3[] der Größe n1 + n2.
- Durchlaufen Sie gleichzeitig arr1[] und arr2[].
- Wählen Sie das kleinere der aktuellen Elemente in arr1[] und arr2[], kopieren Sie dieses kleinere Element an die nächste Position in arr3[] und bewegen Sie sich in arr3[] und dem Array, dessen Element ausgewählt wird, weiter.
- Wenn noch Elemente in arr1[] oder arr2[] vorhanden sind, kopieren Sie diese auch in arr3[].
Das folgende Bild ist ein Probelauf des obigen Ansatzes:
Unten ist die Implementierung des obigen Ansatzes:
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
?>
Ausgabe:
Array after merging 1 2 3 4 5 6 7 8
Zeitkomplexität: O(n1 + n2) Hilfsraum
: O(n1 + n2)
Methode 3: Verwenden von Karten (O(nlog(n) + mlog(m)) Zeit und O(N) zusätzlicher Raum)
- Fügen Sie Elemente beider Arrays als Schlüssel in eine Map ein.
- Drucken Sie die Schlüssel der Karte.
Unten ist die Implementierung des obigen Ansatzes.
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 HashMap<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
Ausgabe:
1 2 3 4 5 6 7 8
Zeitkomplexität: O( nlog(n) + mlog(m) ) Hilfsraum
: O(N)
Brocade , Goldman-Sachs , Juniper , Linkedin , Microsoft , Quikr , Snapdeal , Synopsys , Zoho
Verwandte Artikel :
Merge two sorted arrays with O (1) zusätzlicher Leerraum
Verbinde k sortierte Arrays | Satz 1
Dieser Artikel wurde von Sahil Chhabra beigesteuert . Wenn Ihnen GeeksforGeeks gefällt und Sie etwas beitragen möchten, können Sie auch einen Artikel über write.geeksforgeeks.org schreibenoder senden Sie Ihren Artikel per E-Mail an review-team@geeksforgeeks.org. Sehen Sie, wie Ihr Artikel auf der Hauptseite von GeeksforGeeks erscheint, und helfen Sie anderen Geeks.
Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben diskutierten Thema teilen möchten.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .