LeetCode 88. Merge Sorted Array 题解Go 实现从尾部逆向归并两个有序数组【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 88. Merge Sorted Array 展开讲解如何在不借助额外数组的前提下将两个已排序的整数数组合并回第一个数组 nums1。文章以本仓库中该题的标准 Go 解法 88. Merge Sorted Array.go 为主线逐行剖析从尾部向头部放置较大元素的逆向双指针技巧并结合同目录测试文件说明如何验证正确性、覆盖边界场景。读完本文你将掌握经典原地归并的双指针实现、时间与空间复杂度的严谨推导以及面试中容易踩坑的边界细节。题目描述Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.给定两个已经排好序的整数数组 nums1 和 nums2将 nums2 合并进 nums1使 nums1 最终成为一个完整的有序数组。题目对输入做了两点关键约束原文 Note可以假设 nums1 有足够的空间大小大于或等于 m n来容纳来自 nums2 的额外元素nums1 中已经初始化的元素个数为 mnums2 中已经初始化的元素个数为 n。也就是说nums1 的实际容量是 m n其有效前缀长度为 m尾部预留了 n 个空位通常以 0 占位等待被 nums2 的元素填充。合并完成后的 nums1 应恰好包含 m n 个有序元素函数不需要返回任何值结果直接体现在 nums1 中。一个典型的输入输出以本仓库测试用例中最具代表性的数据为例见 88. Merge Sorted Array_test.go输入nums1 [1,2,3,0,0,0]m 3nums2 [2,5,6]n 3输出nums1 [1,2,2,3,5,6]可以看到nums1 的容量 6 m n 3 3数组末尾的 3 个 0 是占位符合并后被 nums2 的元素覆盖。解题思路为什么必须从尾部开始归并直观但低效的正向思路最自然的想法是从头部开始同时遍历两个数组把较小的元素依次写入 nums1 的前面。但这里有一个致命问题nums1 的有效数据占据数组前端如果从前向后写入新写入的元素会覆盖尚未处理的 nums1 元素。为此不得不先把 nums1 的有效部分整体后移、腾出空间每插入一个元素都可能触发大量元素搬移最坏情况下时间复杂度退化到 O(m·n) 甚至更高。逆向双指针让空位决定写入方向原文档给出的核心结论是为了不大量移动元素就要从 2 个数组长度之和的最后一个位置开始依次选取两个数组中大的数从第一个数组的尾巴开始往头放只要循环一次以后就生成了合并以后的数组了。这条思路可以拆解为三步指针定位在 nums1 的尾部下标 m n - 1放置一个写入指针 p同时在 nums1 有效部分的尾部下标 m - 1和 nums2 的尾部下标 n - 1各放一个读取指针。逆向比较每一轮比较 nums1[m-1] 与 nums2[n-1]把较大者写入 nums1[p-1]并让对应的读取指针与写入指针同步前移。收尾兜底当 nums1 的 m 个元素全部搬完而 nums2 还有剩余时把 nums2 剩余元素直接拷贝到 nums1 前端此时前端正好是连续空位。由于写入永远发生在读取指针的后面p 始终不小于 m 或 n 的当前值从尾部写入永远不会覆盖还没处理的元素从而实现了一趟遍历、零额外数组、零元素搬移的原地归并。Go 源码实现逐行解析本仓库的标准实现位于 88. Merge Sorted Array.go完整代码如下package leetcode func merge(nums1 []int, m int, nums2 []int, n int) { for p : m n; m 0 n 0; p-- { if nums1[m-1] nums2[n-1] { nums1[p-1] nums2[n-1] n-- } else { nums1[p-1] nums1[m-1] m-- } } for ; n 0; n-- { nums1[n-1] nums2[n-1] } }下面逐段说明其工作原理。第一段主归并循环for p : m n; m 0 n 0; p-- {p初始化为m n即合并后数组的总长度指向 nums1 容量末尾的下一个位置所以循环体内用p-1作为实际写入下标保证最后一轮写入落在下标 0循环条件是m 0 n 0只要两个数组中还有未处理的元素就继续从后向前归并每轮循环p--写入指针严格左移。循环体内部的比较逻辑if nums1[m-1] nums2[n-1] { nums1[p-1] nums2[n-1] n-- } else { nums1[p-1] nums1[m-1] m-- }比较两个数组当前尾部元素即各自尚未处理的最大值当nums1[m-1] nums2[n-1]时取 nums2 的尾部元素放到nums1[p-1]随后n--把 nums2 的读取指针左移这里使用而非保证两个数组相等元素相遇时优先取 nums2 的从而自然维持了相等元素相对顺序不变的稳定性否则取 nums1 的尾部元素并m--。从整体上看这等价于每次从两个数组剩余元素的最大值中挑一个放到结果尾部因此最终生成的序列必然是整体非递减的。第二段剩余元素兜底拷贝for ; n 0; n-- { nums1[n-1] nums2[n-1] }主循环退出只有两种情况m 0或n 0。其中若m 0而n 0nums1 的有效元素已全部搬完此时 nums1 前端空出的位置恰好是0, n)nums2 剩余元素本就整体有序直接原地顺序拷贝即可注意此时n-1下标恰好落在空位区间内不会覆盖任何有效数据若n 0而m 0nums2 已处理完nums1 剩余元素的位置本来就在最终结果中无需任何操作这也是代码里没有m兜底循环的原因。这段收尾代码是本题最容易遗漏的部分例如nums1为空m 0时整个合并任务就退化为把 nums2 拷贝进 nums1必须由这段循环完成。测试用例与验证方式仓库中的测试组织本仓库为每道题都配套了*_test.go测试文件本题的测试位于 [88. Merge Sorted Array_test.go。测试文件采用question88/para88/ans88的表驱动结构type question88 struct { para88 ans88 } type para88 struct { one []int m int two []int n int } type ans88 struct { one []int }para88封装输入one即 nums1、m、two即 nums2、nans88封装期望输出合并后的完整oneTest_Problem88遍历用例调用merge(p.one, p.m, p.two, p.n)后直接打印输入输出便于人工核对。覆盖的边界场景测试用例刻意选择了两个具有代表性的边界空数组场景para88{[]int{0}, 0, []int{1}, 1}→ 期望[1]。nums1 有效长度为 0容量 1合并结果完全由 nums2 决定用于验证收尾拷贝循环的正确性。常规双数组场景para88{[]int{1, 2, 3, 0, 0, 0}, 3, []int{2, 5, 6}, 3}→ 期望[1, 2, 2, 3, 5, 6]。包含相等元素两个 2用于验证分支的稳定性与去重后的有序性。如何运行测试在仓库根目录执行标准 Go 测试命令即可验证本题及全部题解的正确性与覆盖率# 只运行第 88 题 go test -v ./leetcode/0088.Merge-Sorted-Array/ # 运行整个 leetcode 目录并输出覆盖率仓库 gotest.sh 的做法 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库根目录的 gotest.sh 展示了全量测试的标准写法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...。项目在 go.mod 中声明了模块名github.com/halfrost/LeetCode-Go与 Go 1.19 的最低版本要求按上述命令即可在对应环境直接运行。复杂度分析时间复杂度O(m n)。两个数组中的每个元素恰好被比较一次、写入一次主循环与兜底循环的总迭代次数不超过 m n 次。这正对应原文档要求的算法时间复杂度足够低。空间复杂度O(1)。全程只使用常数个指针变量p、m、n没有申请任何额外数组属于标准的原地in-place算法。相比正向插入时需要反复搬移元素的朴素做法逆向双指针在时间上是最优的必须至少读取每个元素一次空间上也是最优的。易错点与面试延伸忘记兜底拷贝当m 0时主循环一次都不执行若不补上第二段循环结果数组会保持全 0 占位导致错误。写入下标边界循环从p m n出发、用p-1写入若直接以p写入会造成数组越界收尾循环用n-1写入恰好覆盖前端空位。比较符号的选择保证相等元素的稳定性若改成相等场景会优先取 nums1 的元素虽然结果仍有序但在要求稳定的场景下行为不同。不要额外建数组题目要求结果放回 nums1面试官通常期望 O(1) 空间的原地解法新建第三个数组再拷贝回 nums1 虽然可行但不符合题目精神。相关题目联动归并类问题在本仓库中有完整系列可与本题对比学习0021. Merge Two Sorted Lists链表形态下的双指针归并思路同源0023. Merge k Sorted Lists多路归并可借助堆或分治是本题的扩展0004. Median of Two Sorted Arrays在归并思想上进一步要求 O(log(mn))考察二分的高级变体。小结88 题是双指针 逆向填充这一经典套路的最佳入门题从尾部开始、谁大放谁、剩余兜底三行核心逻辑即可完成原地归并。本文结合仓库中的 源码实现 与 表驱动测试完整还原了从题目约束、算法推导到代码验证的闭环。掌握这一模式后再看链表归并、多路归并乃至归并排序都会变得顺理成章。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 88. Merge Sorted Array 题解：Go 实现从尾部逆向归并两个有序数组
LeetCode 88. Merge Sorted Array 题解Go 实现从尾部逆向归并两个有序数组【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 88. Merge Sorted Array 展开讲解如何在不借助额外数组的前提下将两个已排序的整数数组合并回第一个数组 nums1。文章以本仓库中该题的标准 Go 解法 88. Merge Sorted Array.go 为主线逐行剖析从尾部向头部放置较大元素的逆向双指针技巧并结合同目录测试文件说明如何验证正确性、覆盖边界场景。读完本文你将掌握经典原地归并的双指针实现、时间与空间复杂度的严谨推导以及面试中容易踩坑的边界细节。题目描述Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.给定两个已经排好序的整数数组 nums1 和 nums2将 nums2 合并进 nums1使 nums1 最终成为一个完整的有序数组。题目对输入做了两点关键约束原文 Note可以假设 nums1 有足够的空间大小大于或等于 m n来容纳来自 nums2 的额外元素nums1 中已经初始化的元素个数为 mnums2 中已经初始化的元素个数为 n。也就是说nums1 的实际容量是 m n其有效前缀长度为 m尾部预留了 n 个空位通常以 0 占位等待被 nums2 的元素填充。合并完成后的 nums1 应恰好包含 m n 个有序元素函数不需要返回任何值结果直接体现在 nums1 中。一个典型的输入输出以本仓库测试用例中最具代表性的数据为例见 88. Merge Sorted Array_test.go输入nums1 [1,2,3,0,0,0]m 3nums2 [2,5,6]n 3输出nums1 [1,2,2,3,5,6]可以看到nums1 的容量 6 m n 3 3数组末尾的 3 个 0 是占位符合并后被 nums2 的元素覆盖。解题思路为什么必须从尾部开始归并直观但低效的正向思路最自然的想法是从头部开始同时遍历两个数组把较小的元素依次写入 nums1 的前面。但这里有一个致命问题nums1 的有效数据占据数组前端如果从前向后写入新写入的元素会覆盖尚未处理的 nums1 元素。为此不得不先把 nums1 的有效部分整体后移、腾出空间每插入一个元素都可能触发大量元素搬移最坏情况下时间复杂度退化到 O(m·n) 甚至更高。逆向双指针让空位决定写入方向原文档给出的核心结论是为了不大量移动元素就要从 2 个数组长度之和的最后一个位置开始依次选取两个数组中大的数从第一个数组的尾巴开始往头放只要循环一次以后就生成了合并以后的数组了。这条思路可以拆解为三步指针定位在 nums1 的尾部下标 m n - 1放置一个写入指针 p同时在 nums1 有效部分的尾部下标 m - 1和 nums2 的尾部下标 n - 1各放一个读取指针。逆向比较每一轮比较 nums1[m-1] 与 nums2[n-1]把较大者写入 nums1[p-1]并让对应的读取指针与写入指针同步前移。收尾兜底当 nums1 的 m 个元素全部搬完而 nums2 还有剩余时把 nums2 剩余元素直接拷贝到 nums1 前端此时前端正好是连续空位。由于写入永远发生在读取指针的后面p 始终不小于 m 或 n 的当前值从尾部写入永远不会覆盖还没处理的元素从而实现了一趟遍历、零额外数组、零元素搬移的原地归并。Go 源码实现逐行解析本仓库的标准实现位于 88. Merge Sorted Array.go完整代码如下package leetcode func merge(nums1 []int, m int, nums2 []int, n int) { for p : m n; m 0 n 0; p-- { if nums1[m-1] nums2[n-1] { nums1[p-1] nums2[n-1] n-- } else { nums1[p-1] nums1[m-1] m-- } } for ; n 0; n-- { nums1[n-1] nums2[n-1] } }下面逐段说明其工作原理。第一段主归并循环for p : m n; m 0 n 0; p-- {p初始化为m n即合并后数组的总长度指向 nums1 容量末尾的下一个位置所以循环体内用p-1作为实际写入下标保证最后一轮写入落在下标 0循环条件是m 0 n 0只要两个数组中还有未处理的元素就继续从后向前归并每轮循环p--写入指针严格左移。循环体内部的比较逻辑if nums1[m-1] nums2[n-1] { nums1[p-1] nums2[n-1] n-- } else { nums1[p-1] nums1[m-1] m-- }比较两个数组当前尾部元素即各自尚未处理的最大值当nums1[m-1] nums2[n-1]时取 nums2 的尾部元素放到nums1[p-1]随后n--把 nums2 的读取指针左移这里使用而非保证两个数组相等元素相遇时优先取 nums2 的从而自然维持了相等元素相对顺序不变的稳定性否则取 nums1 的尾部元素并m--。从整体上看这等价于每次从两个数组剩余元素的最大值中挑一个放到结果尾部因此最终生成的序列必然是整体非递减的。第二段剩余元素兜底拷贝for ; n 0; n-- { nums1[n-1] nums2[n-1] }主循环退出只有两种情况m 0或n 0。其中若m 0而n 0nums1 的有效元素已全部搬完此时 nums1 前端空出的位置恰好是0, n)nums2 剩余元素本就整体有序直接原地顺序拷贝即可注意此时n-1下标恰好落在空位区间内不会覆盖任何有效数据若n 0而m 0nums2 已处理完nums1 剩余元素的位置本来就在最终结果中无需任何操作这也是代码里没有m兜底循环的原因。这段收尾代码是本题最容易遗漏的部分例如nums1为空m 0时整个合并任务就退化为把 nums2 拷贝进 nums1必须由这段循环完成。测试用例与验证方式仓库中的测试组织本仓库为每道题都配套了*_test.go测试文件本题的测试位于 [88. Merge Sorted Array_test.go。测试文件采用question88/para88/ans88的表驱动结构type question88 struct { para88 ans88 } type para88 struct { one []int m int two []int n int } type ans88 struct { one []int }para88封装输入one即 nums1、m、two即 nums2、nans88封装期望输出合并后的完整oneTest_Problem88遍历用例调用merge(p.one, p.m, p.two, p.n)后直接打印输入输出便于人工核对。覆盖的边界场景测试用例刻意选择了两个具有代表性的边界空数组场景para88{[]int{0}, 0, []int{1}, 1}→ 期望[1]。nums1 有效长度为 0容量 1合并结果完全由 nums2 决定用于验证收尾拷贝循环的正确性。常规双数组场景para88{[]int{1, 2, 3, 0, 0, 0}, 3, []int{2, 5, 6}, 3}→ 期望[1, 2, 2, 3, 5, 6]。包含相等元素两个 2用于验证分支的稳定性与去重后的有序性。如何运行测试在仓库根目录执行标准 Go 测试命令即可验证本题及全部题解的正确性与覆盖率# 只运行第 88 题 go test -v ./leetcode/0088.Merge-Sorted-Array/ # 运行整个 leetcode 目录并输出覆盖率仓库 gotest.sh 的做法 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库根目录的 gotest.sh 展示了全量测试的标准写法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...。项目在 go.mod 中声明了模块名github.com/halfrost/LeetCode-Go与 Go 1.19 的最低版本要求按上述命令即可在对应环境直接运行。复杂度分析时间复杂度O(m n)。两个数组中的每个元素恰好被比较一次、写入一次主循环与兜底循环的总迭代次数不超过 m n 次。这正对应原文档要求的算法时间复杂度足够低。空间复杂度O(1)。全程只使用常数个指针变量p、m、n没有申请任何额外数组属于标准的原地in-place算法。相比正向插入时需要反复搬移元素的朴素做法逆向双指针在时间上是最优的必须至少读取每个元素一次空间上也是最优的。易错点与面试延伸忘记兜底拷贝当m 0时主循环一次都不执行若不补上第二段循环结果数组会保持全 0 占位导致错误。写入下标边界循环从p m n出发、用p-1写入若直接以p写入会造成数组越界收尾循环用n-1写入恰好覆盖前端空位。比较符号的选择保证相等元素的稳定性若改成相等场景会优先取 nums1 的元素虽然结果仍有序但在要求稳定的场景下行为不同。不要额外建数组题目要求结果放回 nums1面试官通常期望 O(1) 空间的原地解法新建第三个数组再拷贝回 nums1 虽然可行但不符合题目精神。相关题目联动归并类问题在本仓库中有完整系列可与本题对比学习0021. Merge Two Sorted Lists链表形态下的双指针归并思路同源0023. Merge k Sorted Lists多路归并可借助堆或分治是本题的扩展0004. Median of Two Sorted Arrays在归并思想上进一步要求 O(log(mn))考察二分的高级变体。小结88 题是双指针 逆向填充这一经典套路的最佳入门题从尾部开始、谁大放谁、剩余兜底三行核心逻辑即可完成原地归并。本文结合仓库中的 源码实现 与 表驱动测试完整还原了从题目约束、算法推导到代码验证的闭环。掌握这一模式后再看链表归并、多路归并乃至归并排序都会变得顺理成章。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考