[LeetCode] Merge Sorted Array

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.

 解题思路：

额外开了空间，不开也可以，但是会比较麻烦。

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int *C = new int[m + n + 1];
        int a = 0, b = 0;
        for(int i = 0;i < m + n;i++)
        {
            if(a < m)
            {
                if(b < n)
                {
                    if(A[a] < B[b])
                        C[i] = A[a++];
                    else
                        C[i] = B[b++];
                }
                else
                    C[i] = A[a++];
            }
            else
            {
                if(b < n)
                    C[i] = B[b++];
                else
                    break;
            }
        }
        for(int i = 0;i < m + n;i++)
            A[i] = C[i];
    }
};