#88. 合并两个有序数组

LeetCode 原题链接

《程序员面试金典》面试题 10.01：合并排序的数组

#题目描述

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

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

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

示例：

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

输入: nums1 = [1], m = 1, nums2 = [], n = 0
输出: [1]

#1. 题型判断

本题要求合并两个已经有序的数组，并且必须把结果原地写回 nums1。

如果从前往后合并，nums1 前面的有效元素可能会被提前覆盖，导致原始数据丢失。由于 nums1 后面预留了 n 个空位，所以可以从后往前放入较大的元素。

这是一道典型的双指针题：分别从 nums1 和 nums2 的有效尾部开始比较，每次把较大的数放到 nums1 当前最后一个待填位置。

#2. 指针含义

使用三个指针：

• p1：指向 nums1 有效元素的最后一个位置，初始为 m - 1。
• p2：指向 nums2 最后一个位置，初始为 n - 1。
• tail：指向 nums1 当前要写入的位置，初始为 m + n - 1。

当前待合并的有效区间是：

• nums1[0...p1]
• nums2[0...p2]

nums1[tail] 是下一次要填入最终结果的位置。

#3. 窗口或区间维护规则

每次比较 nums1[p1] 和 nums2[p2]：

• 如果 nums1[p1] > nums2[p2]，说明 nums1[p1] 是当前两个数组剩余元素中的最大值，把它写入 nums1[tail]，然后 p1--。
• 否则把 nums2[p2] 写入 nums1[tail]，然后 p2--。
• 每写入一个元素后，tail--，表示下一个位置继续向前填。

因为两个数组本身有序，从尾部取较大值放到最终数组尾部，不会影响还没比较的元素。

#4. 答案更新时机

本题没有单独的返回值，答案就是被原地修改后的 nums1。

每一轮比较后，都把当前最大值写入 nums1[tail]，这一步就是在更新答案数组。

当 p2 < 0 时，说明 nums2 已经全部合并完成，nums1 中剩余元素本来就在正确位置，可以直接结束。

当 p1 < 0 但 p2 >= 0 时，说明 nums1 的有效元素已经用完，需要继续把 nums2 剩余元素写入 nums1 前面的位置。

#5. 边界条件与易错点

边界条件：

• 如果 n = 0，nums2 为空，nums1 不需要修改。
• 如果 m = 0，nums1 没有有效元素，需要把 nums2 全部复制进 nums1。
• 如果两个数组有相同元素，任意先放哪一个都可以，结果仍然有序。

易错点：

• 不能从前往后直接写入 nums1，否则可能覆盖 nums1 中还没比较的有效元素。
• 循环条件只需要关注 p2 >= 0。如果 nums2 合并完，nums1 剩余元素已经天然有序，不必继续处理。
• tail 每次写入后都要左移，否则会反复覆盖同一个位置。

#6. 代码实现

#6.1 单循环写法

/**
 * @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) {
  let p1 = m - 1;
  let p2 = n - 1;
  let tail = m + n - 1;

  while (p2 >= 0) {
    // p1 >= 0 表示 nums1 还有未合并的有效元素，才能比较并取 nums1[p1]。
    // 若 p1 < 0，&& 会短路，不再读取 nums1[p1]，直接进入 else 取 nums2 的元素。
    // 因此，这个条件必须配合“if 取 nums1、else 取 nums2”的分支逻辑。
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[tail] = nums1[p1];
      p1--;
    } else {
      nums1[tail] = nums2[p2];
      p2--;
    }

    tail--;
  }
};

#6.2 两阶段写法（更直观）

也可以把合并过程拆成两个阶段：

1. 当 p1 和 p2 都没有越界时，比较两个指针指向的元素，把较大的元素写入 nums1[tail]。
2. 比较结束后，如果 nums2 还有剩余元素，就继续把它们写入 nums1 前面。

不需要单独处理 nums1 的剩余元素，因为它们原本就在 nums1 的前面，并且位置已经正确。

/**
 * @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) {
  let p1 = m - 1;
  let p2 = n - 1;
  let tail = m + n - 1;

  // 两个数组都有剩余元素时，取较大的元素放到末尾
  while (p1 >= 0 && p2 >= 0) {
    if (nums1[p1] > nums2[p2]) {
      nums1[tail] = nums1[p1];
      p1--;
    } else {
      nums1[tail] = nums2[p2];
      p2--;
    }

    tail--;
  }

  // nums2 若有剩余，需要继续写入 nums1
  while (p2 >= 0) {
    nums1[tail] = nums2[p2];
    p2--;
    tail--;
  }
};

#7. 复杂度分析

• 时间复杂度：O(m + n)，每个指针都只会向左移动，两个数组的元素最多各处理一次。
• 空间复杂度：O(1)，只使用了常数个额外变量，合并结果直接写回 nums1。