题解 | #合并两个有序的数组#

题解一：从尾部开始合并
图示：

复杂度分析：
时间复杂度：O(M+N)
空间复杂度：O(1)
实现如下:

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
      int end = m+n-1, i = m-1,j = n-1; //初始化 end,i,j
      while(end!=0 && i>=0 && j>=0){
         if(A[i]>B[j]) A[end--] = A[i--];  //从尾部开始
         else A[end--] = B[j--];
      }
     while(j>=0) A[end--] = B[j--]; // i《0，复制B
     }
};

题解二：新建空间
题解思路：最简单的一种思路，创建一个新数组存放合并后的数组，然后在拷贝到A中
复杂度分析：
时间复杂度：O((M+N))
空间复杂度：O(m+n)
实现如下

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int tmp[m+n];
        int i=0,j =0,k=0;
        while(i<m||j<n){
            if(i==m) tmp[k++] = B[j++];  //A数组到头
            else if(j==n) tmp[k++] = A[i++]; //B数组到头
            else tmp[k++] = A[i] > B[j] ? B[j++]  :A[i++]; //A数组 B数组选小
        }
        for(int c = 0;c<m+n;c++)
            A[c] = tmp[c];  // tmp 拷贝到A
    }
};