教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕《AlgoNote 算法通关手册》中的 0088. 合并两个有序数组题解 展开系统讲解如何在不开辟新数组的前提下将两个有序数组合并为一个有序数组。文章先完整还原题目约束与两个标准示例再深入拆解「从后向前」的双指针逆序归并思路并结合仓库中的归并排序源码、链表归并实现与双指针专题文档阐明该解法与归并排序「合并过程」的底层血缘关系。读完本文你将掌握双指针归并在数组原地合并场景下的核心套路并能随手写出可运行、可 AC 的 Python 解法。题目链接0088. 合并两个有序数组 - 力扣LeetCode本题在仓库中的完整题解docs/solutions/0001-0099/merge-sorted-array.md题目大意描述给定两个有序数组 $nums1$、$nums2$。要求将 $nums2$ 合并到 $nums1$ 中使 $nums1$ 成为一个有序数组。说明给定数组 $nums1$ 的空间大小为 $m n$其中前 $m$ 个位置存放的是 $nums1$ 的元素末尾 $n$ 个位置是留给合并用的空位。$nums2$ 的空间大小为 $n$。这样可以用 $nums1$ 自身的空间来存储最终的有序数组做到原地合并。$nums1.length m n$。$nums2.length n$。$0 \le m, n \le 200$。$1 \le m n \le 200$。$-10^9 \le nums1[i], nums2[j] \le 10^9$。示例示例 1输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6] 解释需要合并 [1,2,3] 和 [2,5,6]。 合并结果是 [1,2,2,3,5,6]其中斜体加粗标注的为 nums1 中的元素。示例 2输入nums1 [1], m 1, nums2 [], n 0 输出[1] 解释需要合并 [1] 和 []。 合并结果是 [1]。本题与仓库中的另一道简单题「0021. 合并两个有序链表」是同一归并思想的「数组版」与「链表版」可对照学习。解题思路思路 1双指针从后向前逆序归并思路分析直接套用归并排序中「两个有序子数组合并」的常规做法——从前往后比较——在这里会遇到一个麻烦$nums1$ 的有效元素占据数组前 $m$ 个位置若从前向后把 $nums2$ 中的较小元素插入到 $nums1$ 前部会覆盖尚未比较的 $nums1$ 元素因此常规做法需要额外开辟一个大小为 $m n$ 的辅助数组空间复杂度为 $O(m n)$。题目特意把 $nums1$ 的长度设置为 $m n$末尾预留了 $n$ 个空位就是引导我们从后向前归并两个数组最大的元素一定放在整个结果数组的最后面而从后向前写入时写的是数组末尾的空位永远不会覆盖 $nums1$ 中还没处理完的有效元素因此可以完全原地完成。具体步骤如下初始化三个指针$index1$ 指向 $nums1$ 有效元素的最后一个位置$m - 1$$index2$ 指向 $nums2$ 的最后一个位置$n - 1$$index$ 指向 $nums1$ 数组的末尾$m n - 1$作为写入位置。从后向前循环比较 $nums1[index1]$ 与 $nums2[index2]$ 的大小谁大就把谁写入 $nums1[index]$同时对应的指针左移每写入一个元素$index$ 也左移一位。循环终止时可能有两种情况$nums2$ 中还有剩余元素此时 $index2 \ge 0$直接把 $nums2$ 剩余部分整体拷贝到 $nums1$ 前面对应位置因为它们必然是最小的几个元素且已有序。$nums1$ 中还有剩余元素无需处理它们本来就已经在自己的位置上。用 $nums1 [1,2,3,0,0,0], m 3,\ nums2 [2,5,6], n 3$ 走一遍轮次index1index2index比较写入 nums1[index]数组状态初始225--[1,2,3,0,0,0]12253 66[1,2,3,0,0,6]22143 55[1,2,3,0,5,6]32033 23[1,2,3,3,5,6]41022 22[1,2,2,3,5,6]50011 22[1,2,2,3,5,6]结束0-10-拷贝剩余[1,2,2,3,5,6]当 $index2$ 变为 $-1$、$nums2$ 全部处理完毕时$nums1$ 中的剩余元素 $[1]$ 天然就在正确位置无需移动合并完成。思路 1代码class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: # 三个指针分别指向 nums1 有效区末尾、nums2 末尾、nums1 数组末尾 index1 m - 1 index2 n - 1 index m n - 1 # 从后向前比较较大的元素写入 nums1 末尾的空位 while index1 0 and index2 0: if nums1[index1] nums2[index2]: nums1[index] nums2[index2] index2 - 1 else: nums1[index] nums1[index1] index1 - 1 index - 1 # nums2 若还有剩余元素都是最小的一批直接拷贝到 nums1 前部 nums1[:index2 1] nums2[:index2 1]思路 1复杂度分析时间复杂度$O(m n)$。$index1$ 与 $index2$ 每轮至少有一个左移一位两个指针总共移动 $m n$ 次末尾的切片拷贝最多再消耗 $O(n)$总体为 $O(m n)$。空间复杂度$O(1)$。代码没有开辟任何新数组只使用了常数个指针变量是真正的原地归并。原题解中标注的 $O(m n)$ 对应的是「从前往后合并、需要额外辅助数组」的朴素做法采用逆序双指针后额外空间可降为 $O(1)$这也是本题面试考察的核心优化点。边界情况与易错点$n 0$$nums2$ 为空while循环直接跳过nums1[:1]的切片也不会覆盖任何元素函数直接返回$nums1$ 保持原样。$m 0$$nums1$ 前部没有有效元素此时index1 -1循环不进入nums1[:index2 1] nums2[:index2 1]会把 $nums2$ 整体拷贝到 $nums1$ 中正好完成合并。相等元素的处理比较时使用nums1[index1] nums2[index2]才取 $nums2$ 的元素否则取 $nums1$ 的相等时优先保留 $nums1$ 的元素。归并本身是稳定操作两个数组中相等的元素先后顺序不会被打乱。切片赋值nums1[:index2 1] nums2[:index2 1]利用了 Python 列表的切片赋值特性原地修改 $nums1$ 的前index2 1个位置无需写循环。深度拓展与仓库源码中归并思想的对应关系1. 归并排序「合并过程」的数组版本题的双指针归并本质上就是归并排序中「合并两个有序子数组」这一核心步骤的特化版本。仓库中 数组归并排序实现 的merge方法展示了标准写法两个指针left_i、right_i分别从两个有序子数组头部出发比较后把较小元素追加到结果数组直到某一侧耗尽再把另一侧剩余元素全部追加def merge(self, left_nums: [int], right_nums: [int]): nums [] left_i, right_i 0, 0 while left_i len(left_nums) and right_i len(right_nums): if left_nums[left_i] right_nums[right_i]: nums.append(left_nums[left_i]) left_i 1 else: nums.append(right_nums[right_i]) right_i 1 while left_i len(left_nums): nums.append(left_nums[left_i]) left_i 1 while right_i len(right_nums): nums.append(right_nums[right_i]) right_i 1 return nums对比可见本题的逆序归并只是把「较小者先写入」翻转成「较大者先写入」并借助 $nums1$ 末尾预留的空位省掉了辅助数组。归并排序的完整思路与复杂度分析可参考仓库文档 docs/01_array/01_07_array_merge_sort.md归并排序总体时间复杂度 $O(n \log n)$、空间复杂度 $O(n)$其合并步骤单次即 $O(m n)$与本题单次合并的复杂度一致。2. 链表版的同源解法同样的「双指针归并」思路在链表中体现为 0021. 合并两个有序链表通过哑节点dummy_head串联两条链每次取较小值的节点接入结果链最后把剩余链整体接上。仓库中 链表归并排序实现 的merge方法即该思想的直接复用def merge(self, left, right): dummy_head ListNode(-1) cur dummy_head while left and right: if left.val right.val: cur.next left left left.next else: cur.next right right right.next cur cur.next if left: cur.next left elif right: cur.next right return dummy_head.next数组与链表的差异只在「内存连续性」数组可以靠下标 $O(1)$ 随机访问任意位置因此能逆序从尾部向前写入链表只能顺序移动指针因而从头部开始用哑节点串联。两道题合在一起恰好覆盖了双指针归并的两种主要形态。3. 本题在仓库知识体系中的定位在 双指针专题文档 中双指针被分为「对撞指针」「快慢指针」「分离双指针」三类。本题属于分离双指针的变体两个指针分别作用在两个数组上$index1$ 作用在 $nums1$$index2$ 作用在 $nums2$协同完成有序数组合并。仓库的分类题目列表 docs/00_preface/00_06_categories_list.md 也将本题标记为「数组、双指针、排序」标签难度为简单是双指针入门阶段强烈推荐的练习。延伸思考从这道题还能学到什么就地操作in-place的价值当题目允许原地修改输入、且输入本身就预留了空间时优先考虑利用这些空间将空间复杂度从 $O(m n)$ 压到 $O(1)$。本题是这一优化最典型的教科书案例。逆序遍历规避覆盖问题前向遍历会覆盖未处理元素时反向思考——从尾部开始、把较大元素往末尾放——往往能巧妙绕开。类似思路也出现在数组原地移动类问题中。归并是高频基本功合并两个有序数组/链表是归并排序、外部排序、合并 K 个有序序列对应仓库题解 merge-k-sorted-lists.md等众多算法的最小组件值得彻底吃透。总结LeetCode 88「合并两个有序数组」用一道简单题承载了两个高频考点双指针归并与原地就地操作。核心解法是从后向前双指针逆序归并时间复杂度 $O(m n)$空间复杂度 $O(1)$。它与仓库中数组归并排序的merge过程、链表归并的实现同出一源掌握了它就掌握了归并家族算法的入口。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐GHelper轻量替代华硕 Armoury Crate 的完整指南GHelper轻量替代华硕 Armoury Crate 的完整指南 Armoury Crate 的安装包有好几百 MB装完多出好几个系统服务开机要等十几秒教程文档知识库LeetCode 88. 合并两个有序数组从归并排序到 O(1) 空间原地三指针解法LeetCode 88. 合并两个有序数组从归并排序到 O 1 空间原地三指针解法 导读本文围绕 leetcode 题解仓库中 problems/88.me文档教程知识库LeetCode 88. Merge Sorted Array 题解Go 实现从尾部逆向归并两个有序数组LeetCode 88. Merge Sorted Array 题解Go 实现从尾部逆向归并两个有序数组 导读 本文围绕 LeetCode 88. Merge示例工程上一篇如何从图表图片中提取数据Engauge Digitizer 图表数字化四步完整指南下一篇如何 3 步跑通 tikuAdapter 题库搜索服务安装、部署与配置完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 AlgoNote 算法通关手册：LeetCode 88 合并两个有序数组（双指针逆序归并）题解全解析
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文围绕《AlgoNote 算法通关手册》中的 0088. 合并两个有序数组题解 展开系统讲解如何在不开辟新数组的前提下将两个有序数组合并为一个有序数组。文章先完整还原题目约束与两个标准示例再深入拆解「从后向前」的双指针逆序归并思路并结合仓库中的归并排序源码、链表归并实现与双指针专题文档阐明该解法与归并排序「合并过程」的底层血缘关系。读完本文你将掌握双指针归并在数组原地合并场景下的核心套路并能随手写出可运行、可 AC 的 Python 解法。题目链接0088. 合并两个有序数组 - 力扣LeetCode本题在仓库中的完整题解docs/solutions/0001-0099/merge-sorted-array.md题目大意描述给定两个有序数组 $nums1$、$nums2$。要求将 $nums2$ 合并到 $nums1$ 中使 $nums1$ 成为一个有序数组。说明给定数组 $nums1$ 的空间大小为 $m n$其中前 $m$ 个位置存放的是 $nums1$ 的元素末尾 $n$ 个位置是留给合并用的空位。$nums2$ 的空间大小为 $n$。这样可以用 $nums1$ 自身的空间来存储最终的有序数组做到原地合并。$nums1.length m n$。$nums2.length n$。$0 \le m, n \le 200$。$1 \le m n \le 200$。$-10^9 \le nums1[i], nums2[j] \le 10^9$。示例示例 1输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6] 解释需要合并 [1,2,3] 和 [2,5,6]。 合并结果是 [1,2,2,3,5,6]其中斜体加粗标注的为 nums1 中的元素。示例 2输入nums1 [1], m 1, nums2 [], n 0 输出[1] 解释需要合并 [1] 和 []。 合并结果是 [1]。本题与仓库中的另一道简单题「0021. 合并两个有序链表」是同一归并思想的「数组版」与「链表版」可对照学习。解题思路思路 1双指针从后向前逆序归并思路分析直接套用归并排序中「两个有序子数组合并」的常规做法——从前往后比较——在这里会遇到一个麻烦$nums1$ 的有效元素占据数组前 $m$ 个位置若从前向后把 $nums2$ 中的较小元素插入到 $nums1$ 前部会覆盖尚未比较的 $nums1$ 元素因此常规做法需要额外开辟一个大小为 $m n$ 的辅助数组空间复杂度为 $O(m n)$。题目特意把 $nums1$ 的长度设置为 $m n$末尾预留了 $n$ 个空位就是引导我们从后向前归并两个数组最大的元素一定放在整个结果数组的最后面而从后向前写入时写的是数组末尾的空位永远不会覆盖 $nums1$ 中还没处理完的有效元素因此可以完全原地完成。具体步骤如下初始化三个指针$index1$ 指向 $nums1$ 有效元素的最后一个位置$m - 1$$index2$ 指向 $nums2$ 的最后一个位置$n - 1$$index$ 指向 $nums1$ 数组的末尾$m n - 1$作为写入位置。从后向前循环比较 $nums1[index1]$ 与 $nums2[index2]$ 的大小谁大就把谁写入 $nums1[index]$同时对应的指针左移每写入一个元素$index$ 也左移一位。循环终止时可能有两种情况$nums2$ 中还有剩余元素此时 $index2 \ge 0$直接把 $nums2$ 剩余部分整体拷贝到 $nums1$ 前面对应位置因为它们必然是最小的几个元素且已有序。$nums1$ 中还有剩余元素无需处理它们本来就已经在自己的位置上。用 $nums1 [1,2,3,0,0,0], m 3,\ nums2 [2,5,6], n 3$ 走一遍轮次index1index2index比较写入 nums1[index]数组状态初始225--[1,2,3,0,0,0]12253 66[1,2,3,0,0,6]22143 55[1,2,3,0,5,6]32033 23[1,2,3,3,5,6]41022 22[1,2,2,3,5,6]50011 22[1,2,2,3,5,6]结束0-10-拷贝剩余[1,2,2,3,5,6]当 $index2$ 变为 $-1$、$nums2$ 全部处理完毕时$nums1$ 中的剩余元素 $[1]$ 天然就在正确位置无需移动合并完成。思路 1代码class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: # 三个指针分别指向 nums1 有效区末尾、nums2 末尾、nums1 数组末尾 index1 m - 1 index2 n - 1 index m n - 1 # 从后向前比较较大的元素写入 nums1 末尾的空位 while index1 0 and index2 0: if nums1[index1] nums2[index2]: nums1[index] nums2[index2] index2 - 1 else: nums1[index] nums1[index1] index1 - 1 index - 1 # nums2 若还有剩余元素都是最小的一批直接拷贝到 nums1 前部 nums1[:index2 1] nums2[:index2 1]思路 1复杂度分析时间复杂度$O(m n)$。$index1$ 与 $index2$ 每轮至少有一个左移一位两个指针总共移动 $m n$ 次末尾的切片拷贝最多再消耗 $O(n)$总体为 $O(m n)$。空间复杂度$O(1)$。代码没有开辟任何新数组只使用了常数个指针变量是真正的原地归并。原题解中标注的 $O(m n)$ 对应的是「从前往后合并、需要额外辅助数组」的朴素做法采用逆序双指针后额外空间可降为 $O(1)$这也是本题面试考察的核心优化点。边界情况与易错点$n 0$$nums2$ 为空while循环直接跳过nums1[:1]的切片也不会覆盖任何元素函数直接返回$nums1$ 保持原样。$m 0$$nums1$ 前部没有有效元素此时index1 -1循环不进入nums1[:index2 1] nums2[:index2 1]会把 $nums2$ 整体拷贝到 $nums1$ 中正好完成合并。相等元素的处理比较时使用nums1[index1] nums2[index2]才取 $nums2$ 的元素否则取 $nums1$ 的相等时优先保留 $nums1$ 的元素。归并本身是稳定操作两个数组中相等的元素先后顺序不会被打乱。切片赋值nums1[:index2 1] nums2[:index2 1]利用了 Python 列表的切片赋值特性原地修改 $nums1$ 的前index2 1个位置无需写循环。深度拓展与仓库源码中归并思想的对应关系1. 归并排序「合并过程」的数组版本题的双指针归并本质上就是归并排序中「合并两个有序子数组」这一核心步骤的特化版本。仓库中 数组归并排序实现 的merge方法展示了标准写法两个指针left_i、right_i分别从两个有序子数组头部出发比较后把较小元素追加到结果数组直到某一侧耗尽再把另一侧剩余元素全部追加def merge(self, left_nums: [int], right_nums: [int]): nums [] left_i, right_i 0, 0 while left_i len(left_nums) and right_i len(right_nums): if left_nums[left_i] right_nums[right_i]: nums.append(left_nums[left_i]) left_i 1 else: nums.append(right_nums[right_i]) right_i 1 while left_i len(left_nums): nums.append(left_nums[left_i]) left_i 1 while right_i len(right_nums): nums.append(right_nums[right_i]) right_i 1 return nums对比可见本题的逆序归并只是把「较小者先写入」翻转成「较大者先写入」并借助 $nums1$ 末尾预留的空位省掉了辅助数组。归并排序的完整思路与复杂度分析可参考仓库文档 docs/01_array/01_07_array_merge_sort.md归并排序总体时间复杂度 $O(n \log n)$、空间复杂度 $O(n)$其合并步骤单次即 $O(m n)$与本题单次合并的复杂度一致。2. 链表版的同源解法同样的「双指针归并」思路在链表中体现为 0021. 合并两个有序链表通过哑节点dummy_head串联两条链每次取较小值的节点接入结果链最后把剩余链整体接上。仓库中 链表归并排序实现 的merge方法即该思想的直接复用def merge(self, left, right): dummy_head ListNode(-1) cur dummy_head while left and right: if left.val right.val: cur.next left left left.next else: cur.next right right right.next cur cur.next if left: cur.next left elif right: cur.next right return dummy_head.next数组与链表的差异只在「内存连续性」数组可以靠下标 $O(1)$ 随机访问任意位置因此能逆序从尾部向前写入链表只能顺序移动指针因而从头部开始用哑节点串联。两道题合在一起恰好覆盖了双指针归并的两种主要形态。3. 本题在仓库知识体系中的定位在 双指针专题文档 中双指针被分为「对撞指针」「快慢指针」「分离双指针」三类。本题属于分离双指针的变体两个指针分别作用在两个数组上$index1$ 作用在 $nums1$$index2$ 作用在 $nums2$协同完成有序数组合并。仓库的分类题目列表 docs/00_preface/00_06_categories_list.md 也将本题标记为「数组、双指针、排序」标签难度为简单是双指针入门阶段强烈推荐的练习。延伸思考从这道题还能学到什么就地操作in-place的价值当题目允许原地修改输入、且输入本身就预留了空间时优先考虑利用这些空间将空间复杂度从 $O(m n)$ 压到 $O(1)$。本题是这一优化最典型的教科书案例。逆序遍历规避覆盖问题前向遍历会覆盖未处理元素时反向思考——从尾部开始、把较大元素往末尾放——往往能巧妙绕开。类似思路也出现在数组原地移动类问题中。归并是高频基本功合并两个有序数组/链表是归并排序、外部排序、合并 K 个有序序列对应仓库题解 merge-k-sorted-lists.md等众多算法的最小组件值得彻底吃透。总结LeetCode 88「合并两个有序数组」用一道简单题承载了两个高频考点双指针归并与原地就地操作。核心解法是从后向前双指针逆序归并时间复杂度 $O(m n)$空间复杂度 $O(1)$。它与仓库中数组归并排序的merge过程、链表归并的实现同出一源掌握了它就掌握了归并家族算法的入口。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐GHelper轻量替代华硕 Armoury Crate 的完整指南GHelper轻量替代华硕 Armoury Crate 的完整指南 Armoury Crate 的安装包有好几百 MB装完多出好几个系统服务开机要等十几秒教程文档知识库LeetCode 88. 合并两个有序数组从归并排序到 O(1) 空间原地三指针解法LeetCode 88. 合并两个有序数组从归并排序到 O 1 空间原地三指针解法 导读本文围绕 leetcode 题解仓库中 problems/88.me文档教程知识库LeetCode 88. Merge Sorted Array 题解Go 实现从尾部逆向归并两个有序数组LeetCode 88. Merge Sorted Array 题解Go 实现从尾部逆向归并两个有序数组 导读 本文围绕 LeetCode 88. Merge示例工程上一篇如何从图表图片中提取数据Engauge Digitizer 图表数字化四步完整指南下一篇如何 3 步跑通 tikuAdapter 题库搜索服务安装、部署与配置完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考