Lintcode: Merge Sorted Array

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

Have you met this question in a real interview? 

Yes

Example

A = [1, 2, 3, empty, empty], B = [4, 5]

After merge, A will be filled as [1, 2, 3, 4, 5]

Note

You may assume that A has enough space (size that is greater or equal to m +n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Tags Expand 

Sorted Array Array

My leetcode same problem solution
The key is to refresh element of A backwards.
Time: O(m+n)
Space: O(1)
Initial codes:

class Solution {
public:
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    void mergeSortedArray(int A[], int m, int B[], int n) {
        // write your code here
        int len = m + n;
        m = m - 1;
        n = n - 1;
        for(int i = len - 1; i >= 0; i--){
            if(m < 0) A[i] = B[n--];
            else if(n < 0) A[i] = A[m--];
            else if(A[m] > B[n]){
                A[i] = A[m--];
            }
            else{
                A[i] = B[n--];
            }
        }
    }
};

Commonly used while loops

class Solution {
public:
    /**
     * @param A: sorted integer array A which has m elements, 
     *           but size of A is m+n
     * @param B: sorted integer array B which has n elements
     * @return: void
     */
    void mergeSortedArray(int A[], int m, int B[], int n) {
        // write your code here
        int num = m + n - 1;
        m--;
        n--;
        while(m >= 0 && n >= 0){
            if(A[m] > B[n]) A[num--] = A[m--];
            else A[num--] = B[n--];
        }
        while(n >= 0){
            A[num--] = B[n--];
        }
    }
};