1.声明一个额外空间。 空间复杂度O(n)

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        vector<int> c(m+n);
        int i = 0, j = 0, k = 0;
        while(i < m && j < n){
            if(A[i] < B[j])c[k++] = A[i++];
            else c[k++] = B[j++];
        }

        while(i < m)c[k++] = A[i++];
        while(j < n)c[k++] = B[j++];

        i = 0;

        for(int x : c){
            A[i++] = x;
        }

    }
};
  1. 一个已知数组从后往前开始赋值,空间复杂度为O(1) 且代码短
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
       int i = m - 1, j = n -1, k = m + n - 1;
       while (i >= 0 && j >= 0){
           A[k--] = A[i] > B[j] ? A[i--] : B[j--];
       }
       while(j >= 0) A[k--] = B[j--];
    }
};