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

心路历程： 加油努力，噢力给！！

做这道题，其实内心是很不平静的，甚至有点排斥自己，为什么这么简单的题，没有被快速做出来。但是，还是很佩服自己，能够静下心来，好好把它做好，做通过了，没有借助外界的任何提示和帮助。

解题思路：

第一种思路：

也是我实现题目通过的思路，就是先把数组挪到后面，再从前往后排序，这种虽然能够排序成功，但是，多用了一次挪动的空间，所有效率有提高空间

第二种思路：

既然是有序数组，那就从后往前排也是有序的，那就直接用A数组后面空闲的空间，让两个A、B数组的指针，从后往前排序进去就好了。所有有了第二种排序的实现方案，不需要像第一种一样，还要挪到A前面的数据到后面。

import java.util.*;
public class Solution {

    public void merge(int A[], int m, int B[], int n) {
        if(n == 0) {
            return;
        }
        if(m == 0) {
            System.arraycopy(B, 0, A, 0, n);
        }

        int aEnd = m-1;
        int bEnd = n -1;
        int mergeEnd = m+n-1;

        while(aEnd >=0 && bEnd >=0) {
            if(A[aEnd]>= B[bEnd]) {
                A[mergeEnd] = A[aEnd];
                mergeEnd--;
                aEnd--;
            } else {
                 A[mergeEnd] = B[bEnd];
                 mergeEnd--;
                 bEnd--;
            }
        }

        while(bEnd >=0) {
            A[mergeEnd] = B[bEnd];
            mergeEnd--;
            bEnd--;
        }
    }

    // 从尾部倒序比较存入最好，尾部有空间，不用异位
    public void merge1(int A[], int m, int B[], int n) {
        if (n == 0) {
            return;
        }
        if (m == 0) {
            System.arraycopy(B, 0, A, 0, n);
            return;
        }

        int t = m + n;
        // 先把A的结果放到尾部，这样方便合并的时候，不用挪位置
        // 也可以直接覆盖掉。
        // 这只效率太低，淘汰！
        // while (i >= 0) {
        //     A[j] = A[i];
        //     A[i] = 0;
        //     i--;
        //     j--;
        // }
        // 改成这种挪动数组，高效！
        System.arraycopy(A, 0, A, n, m);
        
        int i = 0, j = n;
        i = 0;  // A 容器制造
        j = n; //A 数据指针
        int k = 0; //B 数据指针
        while (j < t && k < n) {
            if (A[j] <= B[k]) {
                A[i] = A[j];
                A[j] = 0;
                j++; 
                i++;
            } else {
                A[i] = B[k];
                B[k] = 0;
                k++;
                i++;
            }
        }

        if (j < t) {
            System.arraycopy(A, i, A, i, t-j);
        } else {
            System.arraycopy(B, k, A, i, n-k);
        }
    }
}