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

题目描述
给出一个整数数组A和有序的整数数组B，请将数组B合并到数组A中，变成一个有序的升序数组
注意：
1.可以假设A数组有足够的空间存放B数组的元素，A和 B中初始的元素数目分别为m和n，A的数组空间大小为m+n
2.不要返回合并的数组，返回是空的，将数组B的数据合并到A里面就好了
3.A数组在[0,m-1]的范围也是有序的

例1:
A: [1,2,3,0,0,0]，m=3
B: [2,5,6]，n=3
合并过后A为:
A: [1,2,2,3,5,6]

方法一：暴力求解

求解思路
最直接求解的方法，将A和B数组直接合并成C数组，然后对C数组直接排序即可！

解题代码

class Solution
{
public:
    void merge(int A[], int m, int B[], int n) 
    {
        int clength=m+n;
        int C[clength];//构造一个新的数组
        for(int i=0;i<m;i++)
            C[i]=A[i];
        for(int i=m;i<m+n;i++)
            C[i]=B[i-m];
        //直接对C排序即可！（随便什么冒泡、选择、快排啥的，就当练练手）
        for(int i=0;i<m+n;i++)
            for(int j=i+1;j<m+n;j++)
            {
                if(C[i]>C[j])
                {
                    int temp;
                    temp=C[i];
                    C[i]=C[j];
                    C[j]=temp;
                }
            }
        for(int i=0;i<m+n;i++)
            A[i]=C[i];
    }
};

复杂度分析
时间复杂度：两个循环，O( )
空间复杂度：开辟一个新的数组C，O(n+m)，其中n和m分别为A和B数组的大小

方法二：双指针的思想

求解思路
使用双指针的思想，将A和B数组的指针顶到数组的最后一个位置，然后比较A，B数组的大小，然后从尾到头依次在A数组填入相应的数字，最后如果B数组有些数值比A数组的小，则将B数组直接遍历地填入A数组的头部位置即可。

解题代码

class Solution//参考文卿周槐芳的code
{
public:
    void merge(int A[], int m, int B[], int n) 
    {

    int aPtr = m - 1, bPtr = n - 1;
//  两数组元素从右至左比较，大的去 A 尾部，直至有一方指针到头为止
    for (int ptr = m + n - 1; aPtr >= 0 && bPtr >= 0; ptr--)
    {
        A[ptr] = A[aPtr] > B[bPtr] ? A[aPtr--] : B[bPtr--];
    }
//  A 指针先走完的情况，B 中剩余元素直接copy至 A 对应位置即可；
    while (bPtr >= 0)
    {
        A[bPtr] = B[bPtr];
        bPtr--;
    }   
    }
};

复杂度分析
时间复杂度：一个循环，O(N)
空间复杂度：两个数组，没有引入其他的地址空间，O(1)