合并两个有序数组

方法一：双指针法

解法步骤：

1. 使用两个指针分别指向 nums1 和 nums2 的起始位置。
2. 比较两个指针对应的元素，将较小的元素放入结果数组中，并移动相应的指针。
3. 重复上述步骤，直到一个数组遍历完。
4. 将另一个数组剩余的元素添加到结果数组中。

优点：

• 时间复杂度为 O(m + n)，其中 m 和 n 分别是 nums1 和 nums2 的长度。
• 空间复杂度为 O(m + n)，需要额外的存储空间来保存合并后的数组。

缺点：

• 需要额外的存储空间来保存合并后的数组。

JavaScript 实现：

function merge(nums1, m, nums2, n) {
    let sorted = [];
    let i = 0, j = 0;

    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            sorted.push(nums1[i]);
            i++;
        } else {
            sorted.push(nums2[j]);
            j++;
        }
    }

    while (i < m) {
        sorted.push(nums1[i]);
        i++;
    }

    while (j < n) {
        sorted.push(nums2[j]);
        j++;
    }

    for (let k = 0; k < sorted.length; k++) {
        nums1[k] = sorted[k];
    }
}

方法二：原地合并

解法步骤：

1. 从 nums1 和 nums2 的末尾开始，使用一个指针 p 指向 nums1 的末尾位置。
2. 比较 nums1 和 nums2 的当前元素，将较大的元素放到 nums1 的末尾，并移动相应的指针。
3. 重复上述步骤，直到 nums2 的元素全部合并到 nums1 中。

优点：

• 时间复杂度为 O(m + n)。
• 空间复杂度为 O(1)，不需要额外的存储空间。

缺点：

• 只适用于 nums1 有足够的空间来容纳 nums2 的元素。

JavaScript 实现：

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

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

方法三：使用内置方法

解法步骤：

1. 将 nums2 追加到 nums1 的末尾。
2. 使用 JavaScript 内置的 sort 方法对合并后的数组进行排序。

优点：

• 实现简单，代码简洁。

缺点：

• 时间复杂度为 O((m + n) log(m + n))，因为 sort 方法的时间复杂度通常是 O(n log n)。
• 空间复杂度取决于 sort 方法的实现，可能会有额外的空间开销。

JavaScript 实现：

function merge(nums1, m, nums2, n) {
    nums1.length = m; // 确保 nums1 的长度为 m
    nums2.length = n; // 确保 nums2 的长度为 n
    nums1.push(...nums2);
    nums1.sort((a, b) => a - b);
}