88. 合并两个有序数组

[Geekhyt]

原题链接

逆向双指针

1. 借助双指针，原地修改，从后往前遍历数组，因为 nums1 的空间集中在尾部，从前往后可能会导致原有的数组元素被破坏
2. 初始化 i、j 分别指向初始化元素的末尾位置，k 指向最终的 nums1 数组末尾位置
3. 每次遍历时比较值的大小，进行填充即可
4. 直到 i 和 j 都小于 0 时，遍历结束，返回 nums1

const merge = function(nums1, m, nums2, n) {
    let i = m - 1
    let j = n - 1
    let k = m + n - 1
    while (i >= 0 || j >= 0) {
        if(i < 0) {
            nums1[k--] = nums2[j--]
        }
        else if (j < 0) {
            nums1[k--] = nums1[i--]
        }
        else if (nums1[i] < nums2[j]) {
            nums1[k--] = nums2[j--]
        } else {
            nums1[k--] = nums1[i--]
        }
    }
    return nums1
}

• 时间复杂度：O(m + n)
• 空间复杂度：O(1)

[GTRgoSky]

应该可以不判断 i，因为当j< 0 后剩下nums [0, i] 是默认顺序排的可以省略