merge sorted array

merge sorted array

Good problem

We always want to resolve the problem from head to tail. This time we need to solve this problem from back to save time complexity.

 1 class Solution {
 2 public:
 3     void merge(int A[], int m, int B[], int n) {
 4         if ( n == 0 ) {
 5             return;
 6         }
 7         int k = m+n-1;
 8         int i = m-1;
 9         int j = n-1;
10         while ( j >= 0 ) {
11             if ( i >= 0 && A[i] > B[j] ) {
12                 A[k--] = A[i--];
13             } else {
14                 A[k--] = B[j--]; 
15             }
16         }
17     }
18 };

Loading Disqus comments...
Table of Contents