LeetCode 88 合并两个有序数组：python3 题解

目录

• 1. 题目解读
• 2. 思路分析
  • 方法一：直接合并后排序（最简单，但效率低）
  • 方法二：双指针 - 从前向后（需要额外空间）
  • 方法三：双指针 - 从后向前（最优解）⭐
• 3. 图解演示（方法三）
• 4. 代码实现 (Python 3)
  • 代码关键点注释解析：
• 5. 复杂度分析
• 6. 总结与进阶思考

---

1. 题目解读

题目目标：
你有两个已经排好序（非递减顺序，即从小到大）的数组 nums1 和 nums2。你需要把 nums2 的所有元素合并到 nums1 中，并且合并后的 nums1 依然保持有序。

关键约束：

1. 原地修改：结果必须存储在 nums1 中，不能返回新数组。
2. 空间预留：nums1 的初始长度是 m + n。其中前 m 个元素是有效数据，后 n 个元素是 0（占位符），专门用来存放 nums2 的数据。
3. 时间复杂度：进阶要求是 \(O(m + n)\)。

输入示例：

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

输出：

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

---

2. 思路分析

这道题主要有三种解法，从简单到最优，我们逐一分析。

方法一：直接合并后排序（最简单，但效率低）

思路：
既然 nums1 后面有足够的空间，我们直接把 nums2 的所有元素复制到 nums1 的末尾，然后调用排序函数对整个 nums1 进行排序。

代码逻辑：

1. nums1[m:] = nums2 (把 nums2 接在 nums1 后面)
2. nums1.sort() (排序)

优缺点：

• ✅ 优点：代码极其简单，一行就能写完。
• ❌ 缺点：没有利用两个数组原本就是有序的这个特性。时间复杂度取决于排序算法，通常是 \(O((m+n) \log (m+n))\)，不满足进阶的 \(O(m+n)\) 要求。

方法二：双指针 - 从前向后（需要额外空间）

思路：
这是归并排序的标准合并步骤。

1. 创建一个临时数组 temp。
2. 设置两个指针 p1 指向 nums1 开头，p2 指向 nums2 开头。
3. 比较 p1 和 p2 指向的元素，把较小的放入 temp，并移动对应指针。
4. 最后把 temp 复制回 nums1。

优缺点：

• ✅ 优点：时间复杂度是 \(O(m+n)\)，逻辑直观。
• ❌ 缺点：需要 \(O(m+n)\) 的额外空间来存储 temp 数组。题目要求“原地修改”，虽然这种方法能过，但不是空间最优解。
• ❌ 为什么不能直接在 nums1 上从前向后覆盖？
  如果在 nums1 上直接从前往后覆盖，会覆盖掉 nums1 中还没有处理的元素。例如 nums1=[10, 0], nums2=[5]。如果把 5 放到 nums1[0]，原来的 10 就丢了。

方法三：双指针 - 从后向前（最优解）⭐

思路：
既然 nums1 的末尾是空的（预留了空间），我们可以利用这个空间，从后往前填充数据。

1. 设置三个指针：
   • p1：指向 nums1 有效元素的最后一个（索引 m-1）。
   • p2：指向 nums2 的最后一个（索引 n-1）。
   • p：指向 nums1 的最末尾（索引 m+n-1），这是我们要填充的位置。
2. 比较 nums1[p1] 和 nums2[p2]：
   • 谁大，就把谁放到 nums1[p] 的位置。
   • 然后移动对应的指针（p1 或 p2 减 1，p 也减 1）。
3. 重复上述过程，直到 nums2 中的元素全部处理完。

为什么从后向前更好？

• 因为 nums1 的末尾是空的，我们往里面填数据不会覆盖 nums1 前面还没处理的有效数据。
• 如果 nums1 的元素先处理完了，剩下的 nums2 元素直接填入前面即可。
• 如果 nums2 的元素先处理完了，剩下的 nums1 元素本来就在正确的位置上，不需要移动。

优缺点：

• ✅ 优点：时间复杂度 \(O(m+n)\)，空间复杂度 \(O(1)\)（完全原地修改）。
• ✅ 符合：题目所有的进阶要求。

---

3. 图解演示（方法三）

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

初始状态：

nums1: [1, 2, 3, 0, 0, 0]^           ^p1          p (m+n-1)
nums2: [2, 5, 6]^p2

第一步：比较 nums1[p1]=3 和 nums2[p2]=6。6 更大。
将 6 放入 nums1[p]。

nums1: [1, 2, 3, 0, 0, 6]^           ^p1          p
nums2: [2, 5, 6]^p2

(指针都向前移一位)

第二步：比较 nums1[p1]=3 和 nums2[p2]=5。5 更大。
将 5 放入 nums1[p]。

nums1: [1, 2, 3, 0, 5, 6]^        ^p1       p
nums2: [2, 5, 6]^p2

第三步：比较 nums1[p1]=3 和 nums2[p2]=2。3 更大。
将 3 放入 nums1[p]。

nums1: [1, 2, 3, 3, 5, 6]^     ^p1    p
nums2: [2, 5, 6]^p2

...以此类推，直到 nums2 为空。

---

4. 代码实现 (Python 3)

这里提供方法三（双指针从后向前）的代码，这是面试和实际工程中最推荐的写法。

from typing import Listclass Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""将 nums2 合并到 nums1 中，保持有序。使用双指针从后向前遍历，实现 O(1) 空间复杂度。"""# 初始化三个指针# p1 指向 nums1 有效元素的最后一个p1 = m - 1# p2 指向 nums2 的最后一个p2 = n - 1# p 指向 nums1 的最后一个位置（即 m + n - 1）p = m + n - 1# 当 nums2 还有元素未处理时，继续循环# 如果 nums2 处理完了 (p2 < 0)，说明剩下的 nums1 元素已经在正确位置，无需操作while p2 >= 0:# 情况 1：nums1 还有元素，且 nums1 当前元素 大于 nums2 当前元素# 注意：必须先判断 p1 >= 0，防止数组越界if p1 >= 0 and nums1[p1] > nums2[p2]:nums1[p] = nums1[p1]  # 将 nums1 的大元素放到末尾p1 -= 1               # nums1 指针前移else:# 情况 2：nums2 当前元素 大于等于 nums1 当前元素# 或者 nums1 已经遍历完了 (p1 < 0)，只能取 nums2 的元素nums1[p] = nums2[p2]  # 将 nums2 的大元素放到末尾p2 -= 1               # nums2 指针前移# 填充位置指针前移p -= 1# --- 测试代码 (本地运行时需要，提交 LeetCode 时不需要) ---
if __name__ == "__main__":sol = Solution()nums1 = [1, 2, 3, 0, 0, 0]m = 3nums2 = [2, 5, 6]n = 3sol.merge(nums1, m, nums2, n)print(f"合并结果：{nums1}")  # 输出：[1, 2, 2, 3, 5, 6]

代码关键点注释解析：

1. while p2 >= 0:

   • 这是循环的终止条件。为什么只判断 p2？
   • 因为我们的目标是将 nums2 合并进 nums1。
   • 如果 p2 < 0，说明 nums2 的所有元素都已经放入 nums1 了，任务完成。
   • 如果 p1 < 0 但 p2 >= 0，说明 nums1 的有效元素都放好了，但 nums2 还有剩余。此时 else 分支会把 nums2 剩下的元素依次填入 nums1 前端，逻辑依然正确。
   • 如果 p1 先变负，我们不需要把 nums1 剩余元素移动，因为它们本来就在前面，位置是正确的。

2. if p1 >= 0 and nums1[p1] > nums2[p2]:

   • p1 >= 0 是保护条件。当 nums1 的有效元素全部处理完后，p1 会变成 -1。如果不加这个判断，访问 nums1[-1] 可能会取到错误的值（Python 中负索引表示倒数第几个元素），导致逻辑错误。
   • 只有当 nums1 还有元素 且 该元素比 nums2 当前元素大时，我们才从 nums1 取值。否则（包括 nums1 取完了的情况），我们都从 nums2 取值。

3. nums1[p] = ...

   • 我们直接修改 nums1 数组，没有创建新数组，满足 \(O(1)\) 空间复杂度。

---

5. 复杂度分析

针对上述最优解法（方法三）：

• 时间复杂度：\(O(m + n)\)
  • 我们需要遍历 nums1 的有效部分和 nums2 的全部部分。每个元素最多被比较和移动一次。
• 空间复杂度：\(O(1)\)
  • 我们只使用了 p1, p2, p 三个指针变量，没有使用额外的数组空间。

---

6. 总结与进阶思考

1. 核心技巧：遇到“两个有序数组合并”且“其中一个数组有足够尾部空间”时，从后向前双指针是标准解法。
2. 避坑指南：
   • 不要直接 sort()，虽然能过，但面试时会认为你忽略了“有序”这个条件。
   • 不要从前向后合并到 nums1，会覆盖数据。
   • 注意边界条件，特别是 m=0 或 n=0 的情况。本代码中的 while p2 >= 0 和 if p1 >= 0 完美处理了这些边界。
3. 扩展：如果 nums1 没有预留空间怎么办？那就只能使用方法二（创建新数组），或者先扩容 nums1 再使用方法三。