LeetCode合并有序数组问题：为何0未被成功剔除？

问题场景 #

在解决LeetCode的「合并有序数组」问题时，输入([1,2,3,0,0,0], 3, [2,5,6], 3)，代码输出结果为[0,1,2,2,3,5,6]，与预期的[1,2,2,3,5,6]不符。

问题代码 #

/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1, m, nums2, n) {
    nums2.forEach(i => {
        if (i > 0) {
            nums1.push(i)
        }

    })

    nums1.sort()


    for (let i = 0; i < nums1.length; i++) {
        if (nums1[i] == 0) {
            nums1.splice(i, 1)
        }
    }
};

错误原因分析 #

• 不必要的非零判断：代码里if (i > 0)的判断完全多余，题目中nums2的元素可以是0，这个判断会导致nums2中的0被忽略，不过这次输入里nums2没有0，但这个逻辑本身不符合题目要求。
• 数组长度被错误增加：你用nums1.push(i)把nums2的元素加到nums1末尾，导致nums1的长度从原本的m+n（6）变成了m+n+n（9），违背了题目原地修改nums1的要求——题目里nums1的初始长度已经是m+n，后面的0是预留的空位，不需要额外增加长度。
• sort的默认行为隐患：JS的Array.sort()默认是按字符串Unicode码点排序，不是数字排序，虽然这次数字排序结果看起来没问题，但本质上是个隐患，正确的数字排序应该用nums1.sort((a,b) => a - b)。
• 删除0时的索引错误：用for循环遍历删除元素时，splice(i,1)会让数组长度减1，后面的元素会前移，但循环的i还在递增，导致跳过了部分元素。比如原排序后的数组是[0,0,0,1,2,2,3,5,6]，当i=0删除第一个0后，数组变成[0,0,1,...]，i变成1，删除第二个0，数组变成[0,1,...]，i变成2，此时nums1[2]是1，循环继续，最后剩下的那个0就没被遍历到，所以留在了数组里。

修正方案 #

正确的做法应该是利用双指针从后往前填充nums1的空位，避免覆盖未处理的元素，同时不需要排序：

function merge(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // 如果nums2还有剩余元素，全部拷贝到nums1前面
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
}

内容的提问来源于stack exchange，提问作者judgejab