合并两个排序的数组-yiteyi-C++库

给定两个排序的数组，任务是以排序的方式合并它们。 例如：

null

输入：arr1[]={1,3,4,5}，arr2[]={2,4,6,8} 输出：arr3[]={1,2,3,4,4,5,6,8} 输入：arr1[]={5,8,9}，arr2[]={4,7,8} 输出：arr3[]={4,5,7,8,8,9}

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1（O（n1*n2）时间和O（n1+n2）额外空间）

创建大小为n1+n2的数组arr3[]。
将arr1[]的所有n1元素复制到arr3[]
遍历arr2[]并逐个插入元素（如插入排序 )从arr3[]到arr1[]的。这一步需要O（n1*n2）时间。

我们已经在本文中讨论了上述方法的实现用O（1）个额外空间合并两个已排序数组 方法2（O（n1+n2）时间和O（n1+n2）额外空间） 其思想是使用合并排序 .

创建大小为n1+n2的数组arr3[]。
同时遍历arr1[]和arr2[]。
- 在arr1[]和arr2[]中选取较小的当前元素，将此较小的元素复制到arr3[]中的下一个位置，并在arr3[]和选取其元素的数组中向前移动。
如果arr1[]或arr2[]中还有剩余的元素，请在arr3[]中复制它们。

下图是上述方法的试运行：

图片[1]-合并两个排序的数组-yiteyi-C++库

以下是上述方法的实施情况：

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"                                     );                       
                                                 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 "                                     ;                       
                         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>                       

输出：

Array after merging1 2 3 4 5 6 7 8

时间复杂性： O（n1+n2） 辅助空间： O（n1+n2） 方法3：使用映射（O（nlog（n）+mlog（m））时间和O（n）额外空间）

在映射中插入两个数组的元素作为键。
打印地图的钥匙。

下面是上述方法的实现。

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                       

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>                       

输出：

1 2 3 4 5 6 7 8

时间复杂性： O（nlog（n）+mlog（m）） 辅助空间： O（N）锦缎 , 高盛 , 杜松 , 领英 , 微软 , 奎克尔 , Snapdeal , 新思科技 , 百会 相关文章： 用O（1）个额外空间合并两个已排序数组合并k个排序数组|集1 本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章