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

双指针思想

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

如何将两个有序的数组融合到第一个有序的数组中？

• 由于题目中A已经扩容到可以容纳两个数组元素的容量了，多于的元素用了0作为占位符，所以在融合数组时，应该使用下标进行赋值替换操作，而不是用push来进行插入操作，因此需要第三个指针操作最终A数组的下标。
• 由于要替换扩容后的A中的后面为0的占位符，所以元素比较应该从最后一个元素开始，因此初始的A和B的指针应该指向两者最后一个元素，依次遍历将较大的元素替换A中后面的元素。
• 由于最后融合在A中，因此如果最后剩下A中的元素没有遍历完，它已经在A中有序了，无需继续遍历替换，但是如果B中还有元素，还应继续进行遍历替换操作将他们给替换掉。

参考

https://blog.nowcoder.net/n/374f83439d7c4541bf858642c29c144a?f=comment

https://blog.nowcoder.net/n/e6a478783bde4322ab489fc1ba3e6cdb?f=comment

/**
 * 
 * @param A int整型一维数组 
 * @param B int整型一维数组 
 * @return void
 */
function merge( A, m, B, n ) {
    // write code here
    // A和B都是有序的，从这两个数组的最后一个元素开始遍历，将两者中最大的元素依次放到A的末尾
    let i = n-1;
    let j = m-1;
    let k = n+m-1;  // 为了能直接将元素放入A中，而不用临时数组，需要第三个指针
    
    while (i >= 0 && j >= 0) {
        if (A[j] >= B[i]) {
            A[k--] = A[j--];
        }
        else {
            A[k--] = B[i--];
        }
    }

    while (i >= 0) {
        A[k--] = B[i--];  // 如果B中还有元素则继续放入A中，如果A中还有元素则剩下的元素已经在最终的A中有序了。
    }
}
module.exports = {
    merge : merge
};