描述

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

注：

1. A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
2. 不要返回新数组，将数组 B 的数据合并到 A 里面

示例：A=[1,2,3]，B=[2,5,6]合并后为A=[1,2,2,3,5,6]

难点在于如何移动A数组中原有的元素，如果从前往后插入的话，每次插入时A数组都要整体向后移动。

思路1：新数组+三指针

写法1：A数组和B数组比较，结果暂存到C数组中，最后拷贝回A数组

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int[] C = new int[m + n];
        int i = 0;
        int j = 0;
        int k = 0;
        while(i < m && j < n) {
            C[k++] = A[i] <= B[j] ? A[i++] : B[j++];
        }
        while(i < m) {
            C[k++] = A[i++];
        }
        while(j < n) {
            C[k++] = B[j++];
        }
        for(int index = 0; index < m + n; index++) {
            A[index] = C[index];
        }
    }
}

写法2：先将A数组拷贝到C数组，再比较B和C数组，结果存到A数组中

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int[] C = new int[m];
        for(int index = 0; index < m; index++) {
            C[index] = A[index];
        }
        int i = 0;
        int j = 0;
        int k = 0;
        while(i < m && j < n) {
            A[k++] = C[i] <= B[j] ? C[i++] : B[j++];
        }
        while(i < m) {
            A[k++] = C[i++];
        }
        while(j < n) {
            A[k++] = B[j++];
        }
    }
}

思路2：三指针+逆序遍历

从尾部开始比较，A数组后面还剩余n的空间

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int k = n + m - 1;
        m--;
        n--;
        while(m >= 0 && n >= 0) {
            A[k--] = A[m] > B[n] ? A[m--] : B[n--];
        }
        //B数组剩余需要全部插入，A数组剩余不需要再插入
        while(n >= 0) {
            A[k--] = B[n--];
        }
    }
}

思路3：先合并，再排序

将B数组填充到A数组后面，再排序

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        for(int i = 0; i < n; i++) {
            A[i + m] = B[i];
        }
        Arrays.sort(A);
    }
}