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

题目主要信息:

• A与B是两个升序的整型数组，长度分别为$nn$和$mm$
• 需要将数组B的元素合并到数组A中，保证依旧是升序
• 数组A已经开辟了$m+nm+n$的空间，只是前半部分存储的数组A的内容

具体思路:

既然是两个已经排好序的数组，如果可以用新的辅助数组，那很容易我们可以借助归并排序的思想，将排好序的两个子数组合并到一起。但是这道题要求我们在数组A上面添加，那因为数组A后半部分相当于为空，则我们可以考虑逆向使用归并排序思想，从较大的开始排。

• step 1：使用三个指针，i指向数组A的最大元素，j指向数组B的最大元素，k指向数组A空间的结尾处。
• step 2：从两个数组最大的元素开始遍历，直到某一个结束，每次取出较大的一个值放入数组A空间的最后，然后指针一次往前。
• step 3：如果数组B先遍历结束，数组A前半部分已经存在了，不用管；但是如果数组A先遍历结束，则需要把数组B剩余的前半部分依次逆序加入数组A前半部分，类似归并排序最后的步骤。

具体过程可以参考如下图示：

代码实现:

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i = m - 1; //指向数组A的结尾
        int j = n - 1; //指向数组B的结尾
        int k = m + n - 1; //指向数组A空间的结尾处
        while(i >= 0 && j >= 0){ //从两个数组最大的元素开始，直到某一个数组遍历完
            if(A[i] > B[j]) //将较大的元素放到最后
                A[k--] = A[i--];
            else
                A[k--] = B[j--];
        }
        if(i < 0){ //数组A遍历完了，数组B还有，则还需要添加到数组A前面
            while(j >= 0)
                A[k--] = B[j--];
        } //数组B遍历完了，数组A前面正好有，不用再添加
    }
};

复杂度分析：

• 时间复杂度：$O(n+m)O(n+m)$，最坏情况遍历整个数组 A和数组B
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外空间