给定两个排序的数组A和B，其中A在末尾有足够大的缓冲区来容纳B。 按排序将B合并为A。 例如：
null
Input : a[] = {10, 12, 13, 14, 18, NA, NA, NA, NA, NA} b[] = {16, 17, 19, 20, 22};;Output : a[] = {10, 12, 13, 14, 16, 17, 18, 19, 20, 22}
一种方法是通过在数组前面插入较小的元素来合并两个数组，但这种方法的问题是，我们必须在每次插入后将每个元素向右移动。 所以，我们可以通过比较哪一个元素较小，来比较哪一个元素较大，然后将该元素插入到A的末尾。 下面是上述方法的解决方案。
C++
// Merging b[] into a[] #include <bits/stdc++.h> using namespace std; #define NA -1 void sortedMerge( int a[], int b[], int n, int m) { int i = n - 1; int j = m - 1; int lastIndex = n + m - 1; /* Merge a and b, starting from last element in each */ while (j >= 0) { /* End of a is greater than end of b */ if (i >= 0 && a[i] > b[j]) { a[lastIndex] = a[i]; // Copy Element i--; } else { a[lastIndex] = b[j]; // Copy Element j--; } lastIndex--; // Move indices } } /* Helper function to print the array */ void printArray( int *arr, int n) { cout << "Array A after merging B in sorted" " order : " << endl; for ( int i = 0; i < n; i++) cout << arr[i] << " " ; } int main() { int a[] = {10, 12, 13, 14, 18, NA, NA, NA, NA, NA}; int n = 5; int size_a = 10; int b[] = {16, 17, 19, 20, 22}; int m = 5; sortedMerge(a, b, n, m); printArray(a, size_a); return 0; } |
JAVA
// Java program to merge B // into A in sorted order. import java.io.*; class GFG { static int NA =- 1 ; static void sortedMerge( int a[], int b[], int n, int m) { int i = n - 1 ; int j = m - 1 ; int lastIndex = n + m - 1 ; // Merge a and b, starting // from last element in each while (j >= 0 ) { /* End of a is greater than end of b */ if (i >= 0 && a[i] > b[j]) { // Copy Element a[lastIndex] = a[i]; i--; } else { // Copy Element a[lastIndex] = b[j]; j--; } // Move indices lastIndex--; } } // Helper function to print the array static void printArray( int arr[], int n) { System.out.println ( "Array A after merging B in sorted order : " ) ; for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } // Driver code public static void main (String[] args) { int a[] = { 10 , 12 , 13 , 14 , 18 , NA, NA, NA, NA, NA}; int n = 5 ; int size_a = 10 ; int b[] = { 16 , 17 , 19 , 20 , 22 }; int m = 5 ; sortedMerge(a, b, n, m); printArray(a, size_a); } } // This code is contributed by vt_m. |
Python3
# Python3 program to merge B # into A in sorted order. NA = - 1 # Merging b[] into a[] def sortedMerge(a, b, n, m): i = n - 1 j = m - 1 lastIndex = n + m - 1 # Merge a and b, starting from last # element in each while (j > = 0 ) : # End of a is greater than end # of b if (i > = 0 and a[i] > b[j]): # Copy Element a[lastIndex] = a[i] i - = 1 else : # Copy Element a[lastIndex] = b[j] j - = 1 # Move indices lastIndex - = 1 # Helper function to print # the array def printArray(arr, n): print ( "Array A after merging B in sorted order : " ) for i in range ( 0 , n): print (arr[i], end = " " ) size_a = 10 a = [ 10 , 12 , 13 , 14 , 18 , NA, NA, NA, NA, NA] n = 5 b = [ 16 , 17 , 19 , 20 , 22 ] m = 5 sortedMerge(a, b, n, m) printArray(a, size_a) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# program to merge B into A in // sorted order. using System; class GFG { static int NA =-1; static void sortedMerge( int []a, int []b, int n, int m) { int i = n - 1; int j = m - 1; int lastIndex = n + m - 1; // Merge a and b, starting // from last element in each while (j >= 0) { /* End of a is greater than end of b */ if (i >= 0 && a[i] > b[j]) { // Copy Element a[lastIndex] = a[i]; i--; } else { // Copy Element a[lastIndex] = b[j]; j--; } // Move indices lastIndex--; } } // Helper function to print the array static void printArray( int []arr, int n) { Console.WriteLine ( "Array A after " + "merging B in sorted order : " ) ; for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } // Driver code public static void Main () { int []a = {10, 12, 13, 14, 18, NA, NA, NA, NA, NA}; int n = 5; int size_a = 10; int []b = {16, 17, 19, 20, 22}; int m = 5; sortedMerge(a, b, n, m); printArray(a, size_a); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to merge B into A in // sorted order. // Merging b[] into a[] function sortedMerge( $a , $b , $n , $m ) { $i = $n - 1; $j = $m - 1; $lastIndex = $n + $m - 1; /* Merge a and b, starting from last element in each */ while ( $j >= 0) { /* End of a is greater than end of b */ if ( $i >= 0 && $a [ $i ] > $b [ $j ]) { $a [ $lastIndex ] = $a [ $i ]; // Copy Element $i --; } else { $a [ $lastIndex ] = $b [ $j ]; // Copy Element $j --; } $lastIndex --; // Move indices } return $a ; } /* Helper function to print the array */ function printArray( $arr , $n ) { echo "Array A after merging B in sorted" ; echo " order : " ; for ( $i = 0; $i < $n ; $i ++) echo $arr [ $i ] . " " ; } // Driver Code $a = array (10, 12, 13, 14, 18, -1, -1, -1, -1, -1); $n = 5; $size_a = 10; $b = array (16, 17, 19, 20, 22); $m = 5; $c = sortedMerge( $a , $b , $n , $m ); printArray( $c , $size_a ); // This code is contributed by Rajput-Ji. ?> |
Javascript
<script> // Javascript program to merge B into A in // sorted order. // Merging b[] into a[] function sortedMerge(a, b, n, m) { let i = n - 1; let j = m - 1; let lastIndex = n + m - 1; /* Merge a and b, starting from last element in each */ while (j >= 0) { /* End of a is greater than end of b */ if (i >= 0 && a[i] > b[j]) { a[lastIndex] = a[i]; // Copy Element i--; } else { a[lastIndex] = b[j]; // Copy Element j--; } lastIndex--; // Move indices } return a; } /* Helper function to print the array */ function printArray(arr, n) { document.write( "Array A after merging B in sorted" ); document.write( " order : <br>" ); for (let i = 0; i < n; i++) document.write(arr[i] + " " ); } // Driver Code let a = [10, 12, 13, 14, 18, -1, -1, -1, -1, -1]; let n = 5; let size_a = 10; let b = new Array(16, 17, 19, 20, 22); let m = 5; let c = sortedMerge(a, b, n, m); printArray(c, size_a); // This code is contributed by gfgking. </script> |
输出：
Array A after merging B in sorted order : 10 12 13 14 16 17 18 19 20 22
时间复杂度为O（m+n）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
