目录
- 1. 题目解读
- 2. 思路分析
- 方法一：直接合并后排序（最简单，但效率低）
- 方法二：双指针 - 从前向后（需要额外空间）
- 方法三：双指针 - 从后向前（最优解）⭐
- 3. 图解演示（方法三）
- 4. 代码实现 (Python 3)
- 5. 复杂度分析
- 6. 总结与进阶思考
1. 题目解读
题目目标：
你有两个已经排好序（非递减顺序，即从小到大）的数组 nums1 和 nums2。你需要把 nums2 的所有元素合并到 nums1 中，并且合并后的 nums1 依然保持有序。
关键约束：
- 原地修改：结果必须存储在 nums1 中，不能返回新数组。
- 空间预留：nums1 的初始长度是 m + n。其中前 m 个元素是有效数据，后 n 个元素是 0（占位符），专门用来存放 nums2 的数据。
- 时间复杂度：进阶要求是 \(O(m + n)\)。
输入示例：- nums1 = [1, 2, 3, 0, 0, 0], m = 3
- nums2 = [2, 5, 6], n = 3
这道题主要有三种解法，从简单到最优，我们逐一分析。
方法一：直接合并后排序（最简单，但效率低）
思路：
既然 nums1 后面有足够的空间，我们直接把 nums2 的所有元素复制到 nums1 的末尾，然后调用排序函数对整个 nums1 进行排序。
代码逻辑：
- nums1[m:] = nums2 (把 nums2 接在 nums1 后面)
- nums1.sort() (排序)
优缺点：
- ✅ 优点：代码极其简单，一行就能写完。
- ❌ 缺点：没有利用两个数组原本就是有序的这个特性。时间复杂度取决于排序算法，通常是 \(O((m+n) \log (m+n))\)，不满足进阶的 \(O(m+n)\) 要求。
方法二：双指针 - 从前向后（需要额外空间）
思路：
这是归并排序的标准合并步骤。
- 创建一个临时数组 temp。
- 设置两个指针 p1 指向 nums1 开头，p2 指向 nums2 开头。
- 比较 p1 和 p2 指向的元素，把较小的放入 temp，并移动对应指针。
- 最后把 temp 复制回 nums1。
优缺点：
- ✅ 优点：时间复杂度是 \(O(m+n)\)，逻辑直观。
- ❌ 缺点：需要 \(O(m+n)\) 的额外空间来存储 temp 数组。题目要求“原地修改”，虽然这种方法能过，但不是空间最优解。
- ❌ 为什么不能直接在 nums1 上从前向后覆盖？
如果在 nums1 上直接从前往后覆盖，会覆盖掉 nums1 中还没有处理的元素。例如 nums1=[10, 0], nums2=[5]。如果把 5 放到 nums1[0]，原来的 10 就丢了。
方法三：双指针 - 从后向前（最优解）⭐
思路：
既然 nums1 的末尾是空的（预留了空间），我们可以利用这个空间，从后往前填充数据。
- 设置三个指针：
- p1：指向 nums1 有效元素的最后一个（索引 m-1）。
- p2：指向 nums2 的最后一个（索引 n-1）。
- p：指向 nums1 的最末尾（索引 m+n-1），这是我们要填充的位置。
- 比较 nums1[p1] 和 nums2[p2]：
- 谁大，就把谁放到 nums1[p] 的位置。
- 然后移动对应的指针（p1 或 p2 减 1，p 也减 1）。
- 重复上述过程，直到 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
将 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
将 3 放入 nums1[p]。- nums1: [1, 2, 3, 3, 5, 6]
- ^ ^
- p1 p
- nums2: [2, 5, 6]
- ^
- p2
4. 代码实现 (Python 3)
这里提供方法三（双指针从后向前）的代码，这是面试和实际工程中最推荐的写法。- from typing import List
- class 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 = 3
- nums2 = [2, 5, 6]
- n = 3
- sol.merge(nums1, m, nums2, n)
- print(f"合并结果：{nums1}") # 输出：[1, 2, 2, 3, 5, 6]
- while p2 >= 0:
- 这是循环的终止条件。为什么只判断 p2？
- 因为我们的目标是将 nums2 合并进 nums1。
- 如果 p2 < 0，说明 nums2 的所有元素都已经放入 nums1 了，任务完成。
- 如果 p1 < 0 但 p2 >= 0，说明 nums1 的有效元素都放好了，但 nums2 还有剩余。此时 else 分支会把 nums2 剩下的元素依次填入 nums1 前端，逻辑依然正确。
- 如果 p1 先变负，我们不需要把 nums1 剩余元素移动，因为它们本来就在前面，位置是正确的。
- if p1 >= 0 and nums1[p1] > nums2[p2]:
- p1 >= 0 是保护条件。当 nums1 的有效元素全部处理完后，p1 会变成 -1。如果不加这个判断，访问 nums1[-1] 可能会取到错误的值（Python 中负索引表示倒数第几个元素），导致逻辑错误。
- 只有当 nums1 还有元素 且 该元素比 nums2 当前元素大时，我们才从 nums1 取值。否则（包括 nums1 取完了的情况），我们都从 nums2 取值。
- nums1[p] = ...
- 我们直接修改 nums1 数组，没有创建新数组，满足 \(O(1)\) 空间复杂度。
5. 复杂度分析
针对上述最优解法（方法三）：
- 时间复杂度：\(O(m + n)\)
- 我们需要遍历 nums1 的有效部分和 nums2 的全部部分。每个元素最多被比较和移动一次。
- 空间复杂度：\(O(1)\)
- 我们只使用了 p1, p2, p 三个指针变量，没有使用额外的数组空间。
6. 总结与进阶思考
- 核心技巧：遇到“两个有序数组合并”且“其中一个数组有足够尾部空间”时，从后向前双指针是标准解法。
- 避坑指南：
- 不要直接 sort()，虽然能过，但面试时会认为你忽略了“有序”这个条件。
- 不要从前向后合并到 nums1，会覆盖数据。
- 注意边界条件，特别是 m=0 或 n=0 的情况。本代码中的 while p2 >= 0 和 if p1 >= 0 完美处理了这些边界。
- 扩展：如果 nums1 没有预留空间怎么办？那就只能使用方法二（创建新数组），或者先扩容 nums1 再使用方法三。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
