Effizientes Zusammenführen von zwei sortierten Arrays mit O(1) zusätzlichem Speicherplatz
Bei zwei sortierten Arrays müssen wir sie in O((n+m)*log(n+m)) Zeit mit O(1) zusätzlichem Platz zu einem sortierten Array zusammenführen, wenn n die Größe des ersten Arrays ist, und m ist die Größe des zweiten Arrays.
Beispiel:
Input: ar1[] = {10};
ar2[] = {2, 3};
Output: ar1[] = {2}
ar2[] = {3, 10}
Input: ar1[] = {1, 5, 9, 10, 15, 20};
ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9}
ar2[] = {10, 13, 15, 20}
Wir haben im folgenden Beitrag eine quadratische Zeitlösung besprochen.
In diesem Beitrag wird eine bessere Lösung diskutiert.
Die Idee: Wir fangen an, Elemente zu vergleichen, die weit voneinander entfernt und nicht benachbart sind.
Für jeden Durchgang berechnen wir die Lücke und vergleichen die Elemente rechts von der Lücke. Bei jedem Durchlauf verringert sich die Lücke auf den Höchstwert der Division durch 2.
Beispiele:
First example:
a1[] = {3 27 38 43},
a2[] = {9 10 82}
Start with
gap = ceiling of n/2 = 4
[This gap is for whole merged array]
3 27 38 43 9 10 82
3 27 38 43 9 10 82
3 10 38 43 9 27 82
gap = 2:
3 10 38 43 9 27 82
3 10 38 43 9 27 82
3 10 38 43 9 27 82
3 10 9 43 38 27 82
3 10 9 27 38 43 82
gap = 1:
3 10 9 27 38 43 82
3 10 9 27 38 43 82
3 9 10 27 38 43 82
3 9 10 27 38 43 82
3 9 10 27 38 43 82
3 9 10 27 38 43 82
Output : 3 9 10 27 38 43 82
Second Example:
a1[] = {10 27 38 43 82},
a2[] = {3 9}
Start with gap = ceiling of n/2 (4):
10 27 38 43 82 3 9
10 27 38 43 82 3 9
10 3 38 43 82 27 9
10 3 9 43 82 27 38
gap = 2:
10 3 9 43 82 27 38
9 3 10 43 82 27 38
9 3 10 43 82 27 38
9 3 10 43 82 27 38
9 3 10 27 82 43 38
9 3 10 27 38 43 82
gap = 1
9 3 10 27 38 43 82
3 9 10 27 38 43 82
3 9 10 27 38 43 82
3 9 10 27 38 43 82
3 9 10 27 38 43 82
3 9 10 27 38 43 82
Output : 3 9 10 27 38 43 82
Unten ist die Umsetzung der obigen Idee:
C++
// Merging two sorted arrays with O(1)
// extra space
#include <bits/stdc++.h>
using namespace std;
// Function to find next gap.
int nextGap(int gap)
{
if (gap <= 1)
return 0;
return (gap / 2) + (gap % 2);
}
void merge(int* arr1, int* arr2, int n, int m)
{
int i, j, gap = n + m;
for (gap = nextGap(gap);
gap > 0; gap = nextGap(gap))
{
// comparing elements in the first array.
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap])
swap(arr1[i], arr1[i + gap]);
// comparing elements in both arrays.
for (j = gap > n ? gap - n : 0;
i < n && j < m;
i++, j++)
if (arr1[i] > arr2[j])
swap(arr1[i], arr2[j]);
if (j < m) {
// comparing elements in the second array.
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap])
swap(arr2[j], arr2[j + gap]);
}
}
}
// Driver code
int main()
{
int a1[] = { 10, 27, 38, 43, 82 };
int a2[] = { 3, 9 };
int n = sizeof(a1) / sizeof(int);
int m = sizeof(a2) / sizeof(int);
// Function Call
merge(a1, a2, n, m);
printf("First Array: ");
for (int i = 0; i < n; i++)
printf("%d ", a1[i]);
printf("\nSecond Array: ");
for (int i = 0; i < m; i++)
printf("%d ", a2[i]);
printf("\n");
return 0;
}
Java
// Java program for Merging two sorted arrays
// with O(1) extra space
public class MergeTwoSortedArrays {
// Function to find next gap.
private static int nextGap(int gap)
{
if (gap <= 1)
return 0;
return (gap / 2) + (gap % 2);
}
private static void merge(int[] arr1,
int[] arr2, int n,
int m)
{
int i, j, gap = n + m;
for (gap = nextGap(gap); gap > 0;
gap = nextGap(gap))
{
// comparing elements in the first
// array.
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap])
{
int temp = arr1[i];
arr1[i] = arr1[i + gap];
arr1[i + gap] = temp;
}
// comparing elements in both arrays.
for (j = gap > n ? gap - n : 0;
i < n && j < m;
i++, j++)
if (arr1[i] > arr2[j])
{
int temp = arr1[i];
arr1[i] = arr2[j];
arr2[j] = temp;
}
if (j < m)
{
// comparing elements in the
// second array.
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap])
{
int temp = arr2[j];
arr2[j] = arr2[j + gap];
arr2[j + gap] = temp;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int[] a1 = { 10, 27, 38, 43, 82 };
int[] a2 = { 3, 9 };
// Function Call
merge(a1, a2, a1.length, a2.length);
System.out.print("First Array: ");
for (int i = 0; i < a1.length; i++) {
System.out.print(a1[i] + " ");
}
System.out.println();
System.out.print("Second Array: ");
for (int i = 0; i < a2.length; i++) {
System.out.print(a2[i] + " ");
}
}
}
// This code is contributed by Vinisha Shah
Python3
# Merging two sorted arrays with O(1)
# extra space
# Function to find next gap.
def nextGap(gap):
if (gap <= 1):
return 0
return (gap // 2) + (gap % 2)
def merge(arr1, arr2, n, m):
gap = n + m
gap = nextGap(gap)
while gap > 0:
# comparing elements in
# the first array.
i = 0
while i + gap < n:
if (arr1[i] > arr1[i + gap]):
arr1[i], arr1[i + gap] = arr1[i + gap], arr1[i]
i += 1
# comparing elements in both arrays.
j = gap - n if gap > n else 0
while i < n and j < m:
if (arr1[i] > arr2[j]):
arr1[i], arr2[j] = arr2[j], arr1[i]
i += 1
j += 1
if (j < m):
# comparing elements in the
# second array.
j = 0
while j + gap < m:
if (arr2[j] > arr2[j + gap]):
arr2[j], arr2[j + gap] = arr2[j + gap], arr2[j]
j += 1
gap = nextGap(gap)
# Driver code
if __name__ == "__main__":
a1 = [10, 27, 38, 43, 82]
a2 = [3, 9]
n = len(a1)
m = len(a2)
# Function Call
merge(a1, a2, n, m)
print("First Array: ", end="")
for i in range(n):
print(a1[i], end=" ")
print()
print("Second Array: ", end="")
for i in range(m):
print(a2[i], end=" ")
print()
# This code is contributed
# by ChitraNayal
C#
// C# program for Merging two sorted arrays
// with O(1) extra space
using System;
class GFG {
// Function to find next gap.
static int nextGap(int gap)
{
if (gap <= 1)
return 0;
return (gap / 2) + (gap % 2);
}
private static void merge(int[] arr1, int[] arr2, int n,
int m)
{
int i, j, gap = n + m;
for (gap = nextGap(gap); gap > 0;
gap = nextGap(gap))
{
// comparing elements in the first
// array.
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap])
{
int temp = arr1[i];
arr1[i] = arr1[i + gap];
arr1[i + gap] = temp;
}
// comparing elements in both arrays.
for (j = gap > n ? gap - n : 0; i < n && j < m;
i++, j++)
if (arr1[i] > arr2[j])
{
int temp = arr1[i];
arr1[i] = arr2[j];
arr2[j] = temp;
}
if (j < m) {
// comparing elements in the
// second array.
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap])
{
int temp = arr2[j];
arr2[j] = arr2[j + gap];
arr2[j + gap] = temp;
}
}
}
}
// Driver code
public static void Main()
{
int[] a1 = { 10, 27, 38, 43, 82 };
int[] a2 = { 3, 9 };
// Function Call
merge(a1, a2, a1.Length, a2.Length);
Console.Write("First Array: ");
for (int i = 0; i < a1.Length; i++) {
Console.Write(a1[i] + " ");
}
Console.WriteLine();
Console.Write("Second Array: ");
for (int i = 0; i < a2.Length; i++) {
Console.Write(a2[i] + " ");
}
}
}
// This code is contributed by Sam007.
PHP
<?php
// Merging two sorted arrays
// with O(1) extra space
// Function to find next gap.
function nextGap($gap)
{
if ($gap <= 1)
return 0;
return ($gap / 2) +
($gap % 2);
}
function merge($arr1, $arr2,
$n, $m)
{
$i;
$j;
$gap = $n + $m;
for ($gap = nextGap($gap);
$gap > 0; $gap = nextGap($gap))
{
// comparing elements
// in the first array.
for ($i = 0; $i + $gap < $n; $i++)
if ($arr1[$i] > $arr1[$i + $gap])
{
$tmp = $arr1[$i];
$arr1[$i] = $arr1[$i + $gap];
$arr1[$i + $gap] = $tmp;
}
// comparing elements
// in both arrays.
for ($j = $gap > $n ? $gap - $n : 0 ;
$i < $n && $j < $m; $i++, $j++)
if ($arr1[$i] > $arr2[$j])
{
$tmp = $arr1[$i];
$arr1[$i] = $arr2[$j];
$arr2[$j] = $tmp;
}
if ($j < $m)
{
// comparing elements in
// the second array.
for ($j = 0; $j + $gap < $m; $j++)
if ($arr2[$j] > $arr2[$j + $gap])
{
$tmp = $arr2[$j];
$arr2[$j] = $arr2[$j + $gap];
$arr2[$j + $gap] = $tmp;
}
}
}
echo "First Array: ";
for ($i = 0; $i < $n; $i++)
echo $arr1[$i]." ";
echo "\nSecond Array: ";
for ($i = 0; $i < $m; $i++)
echo $arr2[$i] . " ";
echo"\n";
}
// Driver code
$a1 = array(10, 27, 38, 43 ,82);
$a2 = array(3,9);
$n = sizeof($a1);
$m = sizeof($a2);
// Function Call
merge($a1, $a2, $n, $m);
// This code is contributed
// by mits.
?>
Javascript
<script>
// Javascript program for Merging two sorted arrays
// with O(1) extra space
// Function to find next gap.
function nextGap(gap)
{
if (gap <= 1)
return 0;
return parseInt(gap / 2, 10) + (gap % 2);
}
function merge(arr1, arr2, n, m)
{
let i, j, gap = n + m;
for (gap = nextGap(gap); gap > 0;
gap = nextGap(gap))
{
// comparing elements in the first
// array.
for (i = 0; i + gap < n; i++)
if (arr1[i] > arr1[i + gap])
{
let temp = arr1[i];
arr1[i] = arr1[i + gap];
arr1[i + gap] = temp;
}
// comparing elements in both arrays.
for (j = gap > n ? gap - n : 0; i < n && j < m;
i++, j++)
if (arr1[i] > arr2[j])
{
let temp = arr1[i];
arr1[i] = arr2[j];
arr2[j] = temp;
}
if (j < m) {
// comparing elements in the
// second array.
for (j = 0; j + gap < m; j++)
if (arr2[j] > arr2[j + gap])
{
let temp = arr2[j];
arr2[j] = arr2[j + gap];
arr2[j + gap] = temp;
}
}
}
}
let a1 = [ 10, 27, 38, 43, 82 ];
let a2 = [ 3, 9 ];
// Function Call
merge(a1, a2, a1.length, a2.length);
document.write("First Array: ");
for (let i = 0; i < a1.length; i++) {
document.write(a1[i] + " ");
}
document.write("</br>");
document.write("Second Array: ");
for (let i = 0; i < a2.length; i++) {
document.write(a2[i] + " ");
}
</script>
Ausgabe
Erste Reihe: 3 9 10 27 38 Zweite Reihe: 43 82
Eine andere Methode in O(m+n) Zeitkomplexität:
Hier verwenden wir die folgende Technik:
Suppose we have a number A and we want to convert it to a number B and there is also a constraint that we can recover number A any time without using other variable.To achieve this we chose a number N which is greater than both numbers and add B*N in A. so A --> A+B*N To get number B out of (A+B*N) we divide (A+B*N) by N. so (A+B*N)/N = B. To get number A out of (A+B*N) we take modulo with N. so (A+B*N)%N = A. -> In short by taking modulo we get old number back and taking divide we new number.
Wir finden zuerst das maximale Element beider Arrays und inkrementieren es um eins, um eine Kollision von 0 und maximalem Element während der Modulo-Operation zu vermeiden. Die Idee ist, beide Arrays gleichzeitig zu durchlaufen. Nehmen wir an, ein Element in a ist a[i] und in b ist b[j] und k ist die Position, an der die nächste Mindestzahl kommt. Aktualisieren Sie nun den Wert a[k], wenn k<n, sonst b[kn], indem Sie min(a[i],b[j])*maximum_element hinzufügen. Nachdem Sie alle Elemente aktualisiert haben, teilen Sie alle Elemente durch maximum_element, damit wir das aktualisierte Array zurückerhalten.
Unten ist die Umsetzung der obigen Idee:
C++
#include <bits/stdc++.h>
using namespace std;
void mergeArray(int a[], int b[], int n, int m)
{
int mx = 0;
// Find maximum element of both array
for (int i = 0; i < n; i++) {
mx = max(mx, a[i]);
}
for (int i = 0; i < m; i++) {
mx = max(mx, b[i]);
}
// increment by one to avoid collision of 0 and maximum
// element of array in modulo operation
mx++;
int i = 0, j = 0, k = 0;
while (i < n && j < m && k < (n + m)) {
// recover back original element to compare
int e1 = a[i] % mx;
int e2 = b[j] % mx;
if (e1 <= e2) {
// update element by adding multiplication
// with new number
if (k < n)
a[k] += (e1 * mx);
else
b[k - n] += (e1 * mx);
i++;
k++;
}
else {
// update element by adding multiplication
// with new number
if (k < n)
a[k] += (e2 * mx);
else
b[k - n] += (e2 * mx);
j++;
k++;
}
}
// process those elements which are left in array a
while (i < n) {
int el = a[i] % mx;
if (k < n)
a[k] += (el * mx);
else
b[k - n] += (el * mx);
i++;
k++;
}
// process those elements which are left in array b
while (j < m) {
int el = b[j] % mx;
if (k < n)
a[k] += (el * mx);
else
b[k - n] += (el * mx);
j++;
k++;
}
// finally update elements by dividing
// with maximum element
for (int i = 0; i < n; i++)
a[i] = a[i] / mx;
// finally update elements by dividing
// with maximum element
for (int i = 0; i < m; i++)
b[i] = b[i] / mx;
return;
}
// Driver Code
int main()
{
int a[] = { 3, 5, 6, 8, 12 };
int b[] = { 1, 4, 9, 13 };
int n = sizeof(a) / sizeof(int); // Length of a
int m = sizeof(b) / sizeof(int); // length of b
// Function Call
mergeArray(a, b, n, m);
cout << "First array : ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
cout << "Second array : ";
for (int i = 0; i < m; i++)
cout << b[i] << " ";
cout << endl;
return 0;
}
Java
import java.io.*;
class GFG{
static void mergeArray(int a[], int b[],
int n, int m)
{
int mx = 0;
// Find maximum element of both array
for(int i = 0; i < n; i++)
{
mx = Math.max(mx, a[i]);
}
for(int i = 0; i < m; i++)
{
mx = Math.max(mx, b[i]);
}
// Increment one two avoid collision of
// 0 and maximum element of array in
// modulo operation
mx++;
int i = 0, j = 0, k = 0;
while (i < n && j < m && k < (n + m))
{
// Recover back original element
// to compare
int e1 = a[i] % mx;
int e2 = b[j] % mx;
if (e1 <= e2)
{
// Update element by adding
// multiplication with new number
if (k < n)
a[k] += (e1 * mx);
else
b[k - n] += (e1 * mx);
i++;
k++;
}
else
{
// Update element by adding
// multiplication with new number
if (k < n)
a[k] += (e2 * mx);
else
b[k - n] += (e2 * mx);
j++;
k++;
}
}
// Process those elements which are
// left in array a
while (i < n)
{
int el = a[i] % mx;
if (k < n)
a[k] += (el * mx);
else
b[k - n] += (el * mx);
i++;
k++;
}
// Process those elements which are
// left in array a
while (j < m)
{
int el = b[j] % mx;
if (k < n)
b[k] += (el * mx);
else
b[k - n] += (el * mx);
j++;
k++;
}
// Finally update elements by dividing
// with maximum element
for(int in = 0; in < n; in++)
a[in] = a[in] / mx;
// Finally update elements by dividing
// with maximum element
for(int in = 0; in < m; in++)
b[in] = b[in] / mx;
return;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 3, 5, 6, 8, 12 };
int b[] = { 1, 4, 9, 13 };
// Length of a
int n = a.length;
// length of b
int m = b.length;
// Function Call
mergeArray(a, b, n, m);
System.out.print("First array : ");
for(int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
System.out.print("Second array : ");
for(int i = 0; i < m; i++)
System.out.print(b[i] + " ");
System.out.println();
}
}
// This code is contributed by yashbeersingh42
C#
using System;
public class GFG{
static void mergeArray(int[] a, int[] b,
int n, int m)
{
int mx = 0;
// Find maximum element of both array
for(int I = 0; I < n; I++)
{
mx = Math.Max(mx, a[I]);
}
for(int I = 0; I < m; I++)
{
mx = Math.Max(mx, b[I]);
}
// Increment one two avoid collision of
// 0 and maximum element of array in
// modulo operation
mx++;
int i = 0, j = 0, k = 0;
while (i < n && j < m && k < (n + m))
{
// Recover back original element
// to compare
int e1 = a[i] % mx;
int e2 = b[j] % mx;
if (e1 <= e2)
{
// Update element by adding
// multiplication with new number
if (k < n)
a[k] += (e1 * mx);
else
b[k - n] += (e1 * mx);
i++;
k++;
}
else
{
// Update element by adding
// multiplication with new number
if (k < n)
a[k] += (e2 * mx);
else
b[k - n] += (e2 * mx);
j++;
k++;
}
}
// Process those elements which are
// left in array a
while (i < n)
{
int el = a[i] % mx;
if (k < n)
a[k] += (el * mx);
else
b[k - n] += (el * mx);
i++;
k++;
}
// Process those elements which are
// left in array a
while (j < m)
{
int el = b[j] % mx;
if (k < n)
b[k] += (el * mx);
else
b[k - n] += (el * mx);
j++;
k++;
}
// Finally update elements by dividing
// with maximum element
for(int In = 0; In < n; In++)
a[In] = a[In] / mx;
// Finally update elements by dividing
// with maximum element
for(int In = 0; In < m; In++)
b[In] = b[In] / mx;
return;
}
// Driver code
static public void Main (){
int[] a = { 3, 5, 6, 8, 12 };
int[] b = { 1, 4, 9, 13 };
// Length of a
int n = a.Length;
// length of b
int m = b.Length;
// Function Call
mergeArray(a, b, n, m);
Console.Write("First array : ");
for(int i = 0; i < n; i++)
Console.Write(a[i] + " ");
Console.WriteLine();
Console.Write("Second array : ");
for(int i = 0; i < m; i++)
Console.Write(b[i] + " ");
Console.WriteLine();
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
function mergeArray(a, b, n, m)
{
let mx = 0;
// Find maximum element of both array
for(let i = 0; i < n; i++)
{
mx = Math.max(mx, a[i]);
}
for(let i = 0; i < m; i++)
{
mx = Math.max(mx, b[i]);
}
// Increment by one to avoid collision
// of 0 and maximum element of array
// in modulo operation
mx++;
let i = 0, j = 0, k = 0;
while (i < n && j < m && k < (n + m))
{
// Recover back original element
// to compare
let e1 = a[i] % mx;
let e2 = b[j] % mx;
if (e1 <= e2)
{
// Update element by adding
// multiplication with new number
if (k < n)
a[k] += (e1 * mx);
else
b[k - n] += (e1 * mx);
i++;
k++;
}
else
{
// Update element by adding
// multiplication with new number
if (k < n)
a[k] += (e2 * mx);
else
b[k - n] += (e2 * mx);
j++;
k++;
}
}
// Process those elements which
// are left in array a
while (i < n)
{
let el = a[i] % mx;
if (k < n)
a[k] += (el * mx);
else
b[k - n] += (el * mx);
i++;
k++;
}
// Process those elements which
// are left in array b
while (j < m)
{
let el = b[j] % mx;
if (k < n)
a[k] += (el * mx);
else
b[k - n] += (el * mx);
j++;
k++;
}
// Finally update elements by dividing
// with maximum element
for(let i = 0; i < n; i++)
a[i] = parseInt(a[i] / mx);
// Finally update elements by dividing
// with maximum element
for(let i = 0; i < m; i++)
b[i] = parseInt(b[i] / mx);
return;
}
// Driver Code
var a = [ 3, 5, 6, 8, 12 ];
var b = [ 1, 4, 9, 13 ];
// Length of a
var n = a.length;
// Length of b
var m = b.length;
// Function Call
mergeArray(a, b, n, m);
document.write("First array : ");
for(let i = 0; i < n; i++)
document.write(a[i] + " ");
document.write('<br>')
document.write("Second array : ");
for(let i = 0; i < m; i++)
document.write(b[i] + " ");
// This code is contributed by Potta Lokesh
</script>
Ausgabe
Erste Reihe: 1 3 4 5 6 Zweite Reihe: 8 9 12 13
Zeitkomplexität: O(m+n)
Wir haben im folgenden Beitrag eine einfache und effiziente Lösung besprochen.
In diesem Beitrag wird eine bessere und einfachere Lösung diskutiert.
Die Idee ist: Wir durchlaufen das erste Array und vergleichen es mit dem ersten Element des zweiten Arrays. Wenn das erste Element des zweiten Arrays kleiner als das erste Array ist, werden wir das zweite Array tauschen und dann sortieren.
- Zuerst müssen wir array1 durchlaufen und es dann mit dem ersten Element von array2 vergleichen.
Wenn es kleiner als array1 ist, tauschen wir beide aus.
- Nach dem Vertauschen sortieren wir das Array2 erneut, sodass das kleinste Element des Array2
an erster Stelle steht, und wir können erneut mit dem Array1 tauschen - Um das Array2 zu sortieren, speichern wir das erste Element von Array2 in einer Variablen und verschieben alle Elemente nach links und speichern
das erste Element in Array2 im letzten.
C++
#include <bits/stdc++.h>
using namespace std;
void mergeArray(int arr1[], int arr2[],
int n, int m)
{
// Now traverse the array1 and if
// arr2 first element
// is less than arr1 then swap
for(int i = 0; i < n; i++)
{
if (arr1[i] > arr2[0])
{
// Swap
int temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
// After swapping we have to sort the array2
// again so that it can be again swap with
// arr1
// We will store the firstElement of array2
// and left shift all the element and store
// the firstElement in arr2[k-1]
int firstElement = arr2[0];
int k;
for(k = 1;
k < m && arr2[k] < firstElement;
k++)
{
arr2[k - 1] = arr2[k];
}
arr2[k - 1] = firstElement;
}
}
// Read the arr1
for(int i = 0; i < n; i++)
{
cout << arr1[i] << " ";
}
cout << endl;
// Read the arr2
for(int i = 0; i < m; i++)
{
cout << arr2[i] << " ";
}
}
// Driver Code
int main()
{
int arr1[] = { 1, 3, 5, 7 };
int arr2[] = { 0, 2, 6, 8, 9 };
int n = arr1.length, m = arr2.length;
mergeArray(arr1, arr2, n, m);
}
// This code is contributed by yashbeersingh42
Java
import java.io.*;
class GFG {
public static void mergeArray(int[] arr1, int[] arr2)
{
// length of first arr1
int n = arr1.length;
// length of second arr2
int m = arr2.length;
// Now traverse the array1 and if
// arr2 first element
// is less than arr1 then swap
for (int i = 0; i < n; i++) {
if (arr1[i] > arr2[0]) {
// swap
int temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
// after swapping we have to sort the array2
// again so that it can be again swap with
// arr1
// we will store the firstElement of array2
// and left shift all the element and store
// the firstElement in arr2[k-1]
int firstElement = arr2[0];
int k;
for (k = 1;
k < m && arr2[k] < firstElement;
k++)
{
arr2[k - 1] = arr2[k];
}
arr2[k - 1] = firstElement;
}
}
// read the arr1
for (int i : arr1) {
System.out.print(i + " ");
}
System.out.println();
// read the arr2
for (int i : arr2) {
System.out.print(i + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr1 = { 1, 3, 5, 7 };
int[] arr2 = { 0, 2, 6, 8, 9 };
mergeArray(arr1, arr2);
}
}
C#
using System;
class GFG{
public static void mergeArray(int[] arr1,
int[] arr2)
{
// Length of first arr1
int n = arr1.Length;
// Length of second arr2
int m = arr2.Length;
// Now traverse the array1 and if
// arr2 first element
// is less than arr1 then swap
for(int i = 0; i < n; i++)
{
if (arr1[i] > arr2[0])
{
// Swap
int temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
// After swapping we have to sort the array2
// again so that it can be again swap with
// arr1
// We will store the firstElement of array2
// and left shift all the element and store
// the firstElement in arr2[k-1]
int firstElement = arr2[0];
int k;
for(k = 1;
k < m && arr2[k] < firstElement;
k++)
{
arr2[k - 1] = arr2[k];
}
arr2[k - 1] = firstElement;
}
}
// Read the arr1
foreach (int i in arr1)
{
Console.Write(i + " ");
}
Console.WriteLine();
// Read the arr2
foreach(int i in arr2)
{
Console.Write(i + " ");
}
}
// Driver Code
static public void Main()
{
int[] arr1 = { 1, 3, 5, 7 };
int[] arr2 = { 0, 2, 6, 8, 9 };
mergeArray(arr1, arr2);
}
}
// This code is contributed by rag2127
Javascript
<script>
function mergeArray(arr1, arr2,
n, m)
{
// Now traverse the array1 and if
// arr2 first element
// is less than arr1 then swap
for(let i = 0; i < n; i++)
{
if (arr1[i] > arr2[0])
{
// Swap
let temp = arr1[i];
arr1[i] = arr2[0];
arr2[0] = temp;
// After swapping we have to sort the array2
// again so that it can be again swap with
// arr1
// We will store the firstElement of array2
// and left shift all the element and store
// the firstElement in arr2[k-1]
let firstElement = arr2[0];
let k;
for(k = 1;
k < m && arr2[k] < firstElement;
k++)
{
arr2[k - 1] = arr2[k];
}
arr2[k - 1] = firstElement;
}
}
// Read the arr1
for(let i = 0; i < n; i++)
{
document.write(arr1[i] + " ");
}
document.write("<br>");
// Read the arr2
for(let i = 0; i < m; i++)
{
document.write(arr2[i] + " ");
}
}
// Driver Code
let arr1 = [ 1, 3, 5, 7 ];
let arr2 = [ 0, 2, 6, 8, 9 ];
let n = 4, m = 5;
mergeArray(arr1, arr2, n, m);
//This code is contributed by Mayank Tyagi
</script>
Ausgabe
0 1 2 3 5 6 7 8 9
Zeitkomplexität: O(n*m)
Raumkomplexität: O(1)
Dieser Artikel wurde von Shlomi Elhaiani beigesteuert . Wenn Ihnen GeeksforGeeks gefällt und Sie etwas beitragen möchten, können Sie auch einen Artikel über write.geeksforgeeks.org schreiben oder Ihren Artikel per E-Mail an Contribute@geeksforgeeks.org senden. 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 teilen Sie weitere Informationen zu dem oben diskutierten Thema mit.
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 .