88. 合并两个有序数组

题目链接：https://leetcode.cn/problems/merge-sorted-array/

代码

/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let p1 = m - 1, p2 = n - 1, p = m + n - 1;
    while (p1 >= 0 && p2 >= 0) {
        if (nums2[p2] > nums1[p1]) {
            nums1[p] = nums2[p2];
            p--;
            p2--;
        } else {
            nums1[p] = nums1[p1];
            p--;
            p1--;
        }
    }
    while(p2 >= 0){
        nums1[p] = nums2[p2];
        p--;
        p2--;
    }
};

思路

使用双指针 + 从后往前覆盖完成原地合并：

1. p1 指向 nums1 有效部分的末尾，即 m - 1
2. p2 指向 nums2 的末尾，即 n - 1
3. p 指向 nums1 整体末尾，即 m + n - 1
4. 比较 nums1[p1] 和 nums2[p2]，把较大的数放到 nums1[p]
5. 放入后移动对应指针，直到某一方遍历结束
6. 如果 nums2 还有剩余，继续拷贝到 nums1 前面

之所以要从后往前填充，是为了避免覆盖掉 nums1 中还没有比较过的有效元素。

关键点

• nums1 末尾预留了足够空间，所以可以直接原地写入

• 从后往前合并可以避免额外开辟数组

• 如果最后 nums1 还有剩余，不需要处理，因为它们本来就在正确位置

• 只有 nums2 剩余时，才需要继续补到前面

• 时间复杂度 $O(m+n)$

• 空间复杂度 $O(1)$