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

/**
 1.正常思路： 
 合并两个数组的正常操作 是：新建一个能容纳 这两个数组的 新数组
 再依次遍历 两个数组，当前最小值 是谁 就取谁
 再移动指针 再比较，直到一个数组取完后，把剩下的数组拼接到已有数组；
 
 2.此题中明确要求 不返回新数组，数据合并到数组A[]中，
 又 A的空间足够大，所以合并过程只能放在A中进行，
 显然比较后的数组放到A数组末尾 才合理
 于是：有每次比较AB数组最大数，取最大数放置于A数组末尾
 一个数组取完后，剩下数组依次复制到 A数组中
 若两个数组处理完之后，A数组还有剩余空间未被填充，则移动数据是的靠前
*/
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int ia = m - 1;
        int ib = n - 1;
        int aLastIdx = A.length - 1;
        // 依次处理 直到一个数组耗尽
        while (ia >= 0 && ib >= 0) {
            if( A[ia] >= B[ib] ) {
                A[aLastIdx--] = A[ia--];
            } else {
                A[aLastIdx--] = B[ib--];
            }
        }
        // A数组 未耗尽
        while( ia >= 0 ) {
            A[aLastIdx--] = A[ia--];
        }
        // B数组 未耗尽
        while( ib >= 0 ) {
            A[aLastIdx--] = B[ib--];
        }
        // 至此 AB数组 均耗尽，判断新数组A，前方是否有剩余空间
        // 若AB刚好填充完 新数组A，那么，此时aLastIdx 值 为 -1
        // 若有空缺则 aLastIdx >= 0
        // 把最后减掉的索引加回来，则 
        // 若AB刚好填充完 新数组A，那么，此时aLastIdx 值 为 0
        // 若有空缺则 aLastIdx > 0
        aLastIdx = aLastIdx + 1;
        if( aLastIdx > 0 ) {
            // 数组前移动, 原有位置 重置为 0
            for (int aFrontIdx = aLastIdx; aFrontIdx < A.length; aFrontIdx++ ) {
                A[aFrontIdx - aLastIdx] = A[aFrontIdx];
                A[aFrontIdx] = 0;
            }
        }
    }
}