Merge Two Sorted Arrays

题目：

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

接口：

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

    }
};

分析：

这道题目好处在于数组A给了足够大的空间，所以可以做inplace的merge。方法是从后往前，找A, B中更大的元素，放进A的末尾。

解答：

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
        while (m > 0 && n > 0) {
            if (A[m - 1] < B[n - 1]) {
                A[m + n - 1] = B[n - 1];
                n--;
            } else {
                A[m + n - 1] = A[m - 1];
                m--;
            }
        }
        while (n > 0) {
            A[n - 1] = B[n - 1];
            n--;
        }
    }
};