02-合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

方法一

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    // 从后往前比较两个数组的元素，将较大的元素放到 nums1 的末尾
    let p1 = m - 1; // nums1 中有效元素的最后一个索引
    let p2 = n - 1; // nums2 中最后一个元素的索引
    let p = m + n - 1; // nums1 合并后数组的最后一个索引

    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--;
    }
}

// 示例调用
const nums1 = [1, 2, 3, 0, 0, 0];
const m = 3;
const nums2 = [2, 5, 6];
const n = 3;
merge(nums1, m, nums2, n);
console.log(nums1);

代码解释

初始化指针：
- p1 指向 nums1 中有效元素的最后一个位置（索引为 m - 1）。
- p2 指向 nums2 中最后一个元素的位置（索引为 n - 1）。
- p 指向 nums1 合并后数组的最后一个位置（索引为 m + n - 1）。
从后往前比较并填充：
- 使用 while 循环，只要 p1 和 p2 都大于等于 0，就比较 nums1[p1] 和 nums2[p2] 的大小。
- 如果 nums1[p1] 大于 nums2[p2]，将 nums1[p1] 放到 nums1[p] 的位置，并将 p1 减 1；否则将 nums2[p2] 放到 nums1[p] 的位置，并将 p2 减 1。
- 每次放置元素后，将 p 减 1。
处理剩余元素：
- 当 p1 小于 0 时，说明 nums1 中的有效元素已经全部处理完，而 nums2 中可能还有剩余元素。
- 使用另一个 while 循环，将 nums2 中剩余的元素依次复制到 nums1 的前面。

复杂度分析

时间复杂度：，因为只需要遍历两个数组一次。
空间复杂度：，只使用了常数级的额外空间。

方法二

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    // 正确截取数组
    let arr1 = nums1.slice(0, m);
    let arr2 = nums2.slice(0, n);
    // 合并数组
    let arr3 = arr1.concat(arr2);
    // 对合并后的数组进行排序
    arr3.sort((a, b) => a - b);
    // 将排序后的数组元素复制回 nums1
    for (let i = 0; i < arr3.length; i++) {
        nums1[i] = arr3[i];
    }
}

// 示例调用
const nums1 = [1, 2, 3, 0, 0, 0];
const m = 3;
const nums2 = [2, 5, 6];
const n = 3;
merge(nums1, m, nums2, n);
console.log(nums1);

代码解释

数组截取：
- let arr1 = nums1.slice(0, m); 从 nums1 里截取前 m 个有效元素。
- let arr2 = nums2.slice(0, n); 从 nums2 里截取所有 n 个元素。
合并数组：
- let arr3 = arr1.concat(arr2); 把 arr1 和 arr2 合并成新数组 arr3。
数组排序：
- arr3.sort((a, b) => a - b); 对合并后的数组 arr3 进行排序，保证元素是非递减顺序。
复制回 nums1：
- 用 for 循环把排序后的 arr3 里的元素逐个复制到 nums1 中。