如何优雅地合并两个有序数组：从基础到进阶的解法探索

创作时间:

作者:

@小白创作中心

如何优雅地合并两个有序数组：从基础到进阶的解法探索

引用

来源

http://www.yuanmayuan.cn/post/215.html

在算法领域中，合并两个有序数组是一个经典且富有挑战性的问题。本文将深入探讨这一问题，从基础实现方法逐步过渡到优化的高效解法，帮助读者全面掌握这一算法技巧。

一、问题描述

合并两个有序数组的目标是将两个数组 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 后面的空余空间，避免使用额外的存储空间。

指针的巧妙利用

我们设置三个指针：

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

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

代码实现

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

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