[88] 合并两个有序数组

题目

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使得 nums1 成为一个有序数组。

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
• 可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

代码实现

下面是合并两个有序数组的 JavaScript 实现：

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
    // 指针初始化指向 nums1 和 nums2 的最后一个元素
    let p1 = m - 1;
    let p2 = n - 1;
    // 合并后的数组的最后一个位置
    let p = m + n - 1;

    // 当 nums2 还有元素未处理时
    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
};

// 使用例子
let nums1 = [1, 2, 3, 0, 0, 0];
let m = 3;
let nums2 = [2, 5, 6];
let n = 3;

merge(nums1, m, nums2, n);
console.log(nums1); // 输出: [1,2,2,3,5,6]

解释

1. 初始化指针：设置三个指针，分别指向 nums1 和 nums2 的末尾以及合并后数组的末尾。
2. 从末尾向前遍历：从数组末尾开始比较 nums1 和 nums2 中的元素，将较大的元素放到合并后的数组末尾。
3. 移动指针：根据比较结果移动相应的指针。
4. 处理剩余元素：因为 nums2 的元素会先遍历完，所以只需要在 nums2 还有未处理元素时进行操作。

这样，最终 nums1 会包含合并后的有序数组。这个方法的时间复杂度为 O(m + n)，空间复杂度为 O(1)，因为我们是在 nums1 中原地合并。