在算法星球上，合并两个有序数组的问题无疑是一个经典而富有挑战性的任务。今天，我们将深入探讨这一问题，带你从基础的实现方法逐步走向优化的高效解法，确保你在面对此类问题时游刃有余。

一、问题描述

合并两个有序数组的目标是将两个数组 nums1 和 nums2 合并为一个有序数组，并将结果存储在 nums1 中。假设 nums1 的长度为 m + n，前 m 个元素是有效数据，而后 n 个元素是可以忽略的空间。nums2 的长度为 n。

输入示例：

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

输出示例：

nums1 = [1, 2, 2, 3, 5, 6]

二、初步解法：使用临时数组

首先，让我们来看看最直观的解法。我们可以创建一个新的数组来存放合并后的结果。这种方法虽然简单易懂，但会占用额外的空间。

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

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

    for (let k = 0; k < m + n; k++) {
        nums1[k] = arr[k];
    }
}

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

这种方法虽然有效，但我们可以进一步优化，减少空间消耗。

三、优化解法：原地合并

接下来，我们引入一种更为高效的策略——原地合并。核心思想是利用 nums1 后面的空余空间，避免使用额外的存储空间。

1. 指针的巧妙利用

我们设置三个指针：

• i 指向 nums1 的有效部分最后一个元素。
• j 指向 nums2 的最后一个元素。
• k 指向 nums1 的最后一个位置。

通过从后向前合并，我们可以避免覆盖尚未处理的元素。

2. 代码实现

下面是采用原地合并的代码实现：

function merge(nums1, m, nums2, n) {
    let i = m - 1;
    let j = n - 1;
    let k = m + n - 1;

    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
}

3. 细节分析

• 从后向前合并：通过从后向前填充 nums1，可以有效避免覆盖问题。
• 特殊情况处理：一旦 nums2 被完全处理，nums1 中剩余的元素自然有序，无需再做处理。

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

四、总结

通过以上两种方法的对比，我们不仅解决了合并两个有序数组的问题，还在过程中学到了如何优化代码的空间复杂度。原地合并的方法在实际应用中更加高效，尤其是当处理大数据量时，节省内存的优势尤为明显。

无论是在编程面试中还是日常开发中，掌握这些算法思路将使你在面对类似问题时更具信心。希望这篇文章能助你一臂之力，让你在算法的海洋中畅游无阻！