[Leetcode 31] 88 Merge Sorted Array

Problem:

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Analysis:

To finish the task efficiently, merge should started from the end of the two arrays.

Note, we can compute the total length of the new array by add A and B's separate length. Also remember to update the index of next elements to be merged

The time complexity is O(n+m), space complexity is O(n+m).

Code:

 1 class Solution {
 2 public:
 3     void merge(int A[], int m, int B[], int n) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int totalLen = m + n, aLast = m-1, bLast = n-1;
 7         
 8         for (int i=m+n-1; i>=0; i--) {
 9             if (aLast < 0)  
10                 A[i] = B[bLast--];
11             else if (bLast < 0)  
12                 A[i] = A[aLast--];
13             else
14                 A[i] = (A[aLast] > B[bLast])?A[aLast--] : B[bLast--];
15         }
16     }
17 };

View Code

Attention: