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

题目主要信息:

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM4. 合并两个有序链表

BM88. 判断是否是回文字符串

BM91. 反转字符串

方法：归并排序思想(推荐使用)

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

思路：

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

具体做法:

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

图示：

alt

Java代码实现:

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

C++代码实现:

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

Python实现代码：

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

复杂度分析：

时间复杂度： $O (n + m)$ ，其中 $m$ 、 $n$ 分别为两个数组的长度，最坏情况遍历整个数组A和数组B
空间复杂度： $O (1)$ ，常数级变量，无额外辅助空间