题目描述:

给定两个已排序整数数组nums1和nums2，合并nums2到nums1中作为一个已排序数组

note

• 在nums1和nums2中初始化元素数量分别为m和n

• 可以假设nums1中有足够的空间(空间大于等于m+n)来容纳来自nums2的元素

Example

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

C++输入格式

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
    }
};

范例一:

void merge(int A[], int m, int B[], int n) {
        int i=m-1;
        int j=n-1;
        int k = m+n-1;
        while(i >=0 && j>=0)
        {
            cout<<"k的变化情况:"<<k<<endl; 
            cout<<"i的变化情况:"<<i<<endl; 
            cout<<"j的变化情况:"<<j<<endl;
            if(A[i] > B[j])
            {
                cout<<"k变化之前的值:"<< k<<endl;
                A[k--] = A[i--];
                cout<<"k变化之后的值:"<< k<<endl;
            }
                
            else
            {
                A[k--] = B[j--];
            }
            cout<<"A[k]的值"<<A[k]<<endl; 
                
        }
        while(j>=0)
            A[k--] = B[j--];
    }

测试用例:

A = [1,2,3], m = 3
B = [2,5,6], n = 3

输出结果:

image.png

解题思路

代码中每一个A[k--] = A[i--]等价于A[k] = A[i]; k--;i--;
子函数的大概意思是说倒序(即数组元素从大到小)循环对比两个数组中值的大小，并把对比中某数组中较大的元素放在A[k]中并使k--，一直循环到i=j=0为止，期间每比较一次其对应的下标减一。当然还有特殊情况len(A)>len(B)和len(A)<len(B)(这句话当伪代码看就行，因为并不是很规范)，我们测试一下这两种情况:
测试用例:

A= {1,2,3,7,8};    //int型数组用于存储输入变量
B= {2,5,6};

若A数组的长度大于B数组时，当B数组中的元素比较完时就结束了。因为当B中元素比较完时，A数组剩余的元素一定全部比B数组中最小的元素都小
输出结果:

image.png

A= {2,5,6};
B= {1,2,3,7,8};   

此时B数组的长度大于A数组，若某一时刻A数组中元素比较完了B数组中还有剩余元素，则把B数组中剩余的元素添加到A数组中，即对应代码部分是:

while(j>=0)
    A[k--] = B[j--];

每个元素变化情况如下表所示

输出结果:

image.png

因为题目中说明nums1中有足够的空间，所以不用考虑nums1中数组的长度。但是我还有一个问题:若A[]中后面有0即A = [1,2,3,0,0,0]，我该怎么计算A中数组的长度。这一步是在进入子函数之前完成的，但是我应该怎么做比较高效的算出A数组的长度呢
可以看出

范例延伸一

if(A[i] > B[j])
{
     A[k--] = A[i--];
}
else
{
   A[k--] = B[j--];
}

可替换为

A[k--] =  A[i] > B[j] ? A[i--] : B[j--];

范例延伸二

还有一种方式更简单。直接在一条语句中全部判断出来，若i<0或者nums1[i] < nums2[j]时，把nums2[j]作为较大元素存入nums1[k]中。对于i<0这种情况的理解是nums2数组的长度大于nums1数组。而对于j<0的情况就不用单独判断了，因为当j<0时就终止循环直接输出nums1即可，因为此时nums1已经具有两个数组的全部元素

class Solution 
{
public:
    void merge(int nums1[], int m, int nums2[], int n) 
    {
        for (int i = m - 1, j = n - 1, k = m + n - 1; k >= 0 && j >= 0; k--)
            nums1[k] = (i < 0 || nums1[i] < nums2[j]) ? nums2[j--] : nums1[i--];
    }
};