LeetCode 88这道题挺有意思它在题库里不算是难题但曝光率很高。我见过不少人把它当成简单题一遍AC就过去了结果在面试里被问到细节时卡壳也见过有人从这道题一路延展出归并排序、多路归并、外部排序的完整知识线。作为每日算法练习里很值得反复做的一道题合并两个有序数组的价值不在题目本身而在它串联起来的一系列基础能力数组原地操作、双指针、逆向思维以及有序数据合并的通用模式。这篇文章我不打算只贴一个最简解法。我会把问题拆开讲清楚暴力解法为什么能用但不够好双指针从前往后为什么需要额外空间从后往前写为什么能省掉空间顺带把边界情况、面试答法、工程延伸一起讲。如果你正在坚持每日算法练习或者准备考察数据结构与算法的岗位面试这篇应该对你有点用。1. 题目拆解与核心考点分析1.1 题目条件里藏着哪些信息题目描述大概是这样的给定两个按非递减顺序排列的整数数组 nums1 和 nums2另有两个整数 m 和 n分别表示两个数组中的元素数目。nums1 的长度是 mn其中前 m 个元素是待合并的有效数据后 n 个位置是占位的 0。要求把 nums2 合并到 nums1 里合并后的数组仍然按非递减顺序排列。注意这里的用词是非递减而不是递增意思是允许相等元素存在。很多人在读题时容易漏掉一个关键点nums1 虽然有 mn 的长度但只有前 m 个数是需要参与排序的有效数据后面 n 个 0 只是占位符并没有实际意义。如果你把后 n 个 0 也当成有效数据参与比较结果看起来可能凑巧正确因为 0 通常最小会被排在前面但数据一复杂就必然出错。我在初学阶段就犯过这个错误拿 [1,2,3,0,0,0] 去合并 [2,5,6]把 0 也当成有效数据参与排序最后输出 [0,0,0,1,2,3]一看就是错的。另一个容易忽略的信息是返回值。题目明确要求将合并结果放到 nums1 中函数不返回新数组。这个要求意味着你不能简单写return sorted(nums1 nums2)即使你在本地测试时这么写完全能打印出正确结果提交到判题系统时也会因为 nums1 没有被真正修改而失败。这是很多新手第一次在这道题上碰壁的地方——本地跑得通提交就报错原因就是没有理解原地修改的要求。1.2 为什么这道题值得反复练如果只看难度LeetCode 88 被归为简单级别。但它在面试和算法训练里的地位不低原因有三点。第一它把双指针这种基础题型体现得非常典型。两个有序序列合并本质上就是维护两个游标每次都取较小的一方放入结果谁的游标动了就继续从那边取。这个模式在后续很多复杂题目里会反复出现比如合并区间、寻找中位数、滑动窗口等都或多或少能看到双指针的思想。第二它考查对数组原地操作的敏感度。数组和链表不同改动数组的一个位置不会像链表那样只需要调整引用。尤其是原地合并时你有没有意识到覆盖顺序会影响到未处理的数据这道题就是一个很好的试金石。能把这个问题想清楚的人通常对内存和数据的理解会更扎实。第三它是归并排序中 merge 步骤的原型也是多路归并的入门钥匙。归并排序在排序算法里稳定且时间复杂度优秀而它最核心的一步就是把两个有序子数组合并成一个有序数组。LeetCode 88 就是这一步的独立实现。掌握了它你再去读归并排序的代码会感觉格外顺畅。1.3 一个容易被忽略的细节占位初始值我前面说后 n 个位置是占位的 0这句描述其实不完全严谨因为测试用例并不保证 nums1 后半部分一定初始化为 0。很多题解在讲解时为了方便会说后面是 0但实际的隐藏测试用例中nums1 可能被初始化为任意值。这道题之所以能用拼接后排序的暴力解法是因为 sort 会对整个数组重排即使后面预填了乱七八糟的值最终结果依然正确。但在双指针解法中如果你没有意识到后半部分是无效区域而是直接把它们当作有效数据参与比较结果就会完全错误。所以在写代码前第一件事就是在脑海中把 nums1 划分成两个区域有效区间 [0, m-1] 和预留区间 [m, mn-1]。所有后续的指针操作都应该基于这个划分。2. 解法演进从暴力到最优2.1 暴力解法拼起来排序能用但不推荐如果面试官没有追问复杂度最直观的解法就是把 nums2 的元素追加到 nums1 后半部分然后对 nums1 整体排序。代码两行就能写完class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: nums1[m:] nums2 nums1.sort()用切片语法可以直接把 nums2 的所有元素赋值到 nums1 下标 m 开始的位置。之后整个 nums1 排序得到的就是合并后的有序数组。这个解法在 LeetCode 上能通过因为题目不要求最优复杂度。时间复杂度是 O((mn)log(mn))空间复杂度取决于排序实现Python 内置的 Timsort 在最好情况下空间开销接近 O(1)但在最坏情况下会需要 O(mn) 的辅助空间。如果 m 和 n 都很大这个差距会变得非常明显。更重要的是它完全浪费了输入数据本身已经有序这个重要信息。两个有序的列表合并只需线性扫描一次就能完成整体排序却是把有序性也推翻了重来等于拿着地图不用非要全城绕一圈。暴力解法还有一个潜在问题如果 nums1 后半部分预留位置中的初始值不是你预期的 0而是其他大数sort 依然能给出正确结果因为排序不在乎原始数据是多少。但如果你在面试中只给出这个解法面试官很可能会接着问为什么不用有序性能不能线性完成所以它适合作为思考起点不适合作为最终答案。2.2 从前往后双指针直观但需要额外空间既然两个数组都已经有序最自然的归并思路是各用一个指针指向数组开头每次比较两个指针指向的元素把较小的写入结果位置然后移动对应指针继续比较。这种从前往后的双指针合并是归并排序 merge 步骤的标准写法。但这里立刻遇到一个矛盾结果要写在 nums1 中。如果从前往后写入位置从下标 0 开始那么当 nums2[j] 小于 nums1[i] 时把 nums2[j] 写到 nums1[k]k 可能大于 i也可能等于 i。如果 k 大于 i覆盖的恰好是 nums1 中还没处理的元素这个元素本来还需要在后面参与比较结果被冲掉了。我举一个具体的例子。假设 nums1[4,5,6,0,0,0]m3nums2[1,2,3]n3。从前往后归并时第一次比较 4 和 11 更小应该放到 nums1[0]但 nums1[0] 原来存的是 4。4 就这么丢了后续无法再参与比较。有人可能会说我可以先保存 4或者先判断 k 和 i 的关系分情况处理。确实可以但分情况会让代码复杂不少而且很容易出错。最简单的解决方式就是先把 nums1 的有效数据复制出来放到临时数组里然后再合并。这样原始数据不会被覆盖归并过程可以放心地在 nums1 上从前往后写。代价是额外 O(m) 的空间。代码逻辑很清晰一个指针指向 nums1 的副本开头一个指针指向 nums2 开头一个指针指向 nums1 的写入位置每次比较取较小值然后移动对应指针。最后如果某个数组还剩元素直接把剩余部分拷贝到结果末尾。class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: nums1_copy nums1[:m] p1 0 p2 0 p 0 while p1 m and p2 n: if nums1_copy[p1] nums2[p2]: nums1[p] nums1_copy[p1] p1 1 else: nums1[p] nums2[p2] p2 1 p 1 if p1 m: nums1[p:] nums1_copy[p1:] if p2 n: nums1[p:] nums2[p2:]2.3 从后往前双指针原地合并的最优解从前往后版本最大的问题在于写入位置会追上有价值的未处理数据。但题目其实给了我们一个隐藏优势nums1 后 n 个位置是空的。既然前方写入会覆盖未处理数据那能不能换个方向从后往前写答案是肯定的。把两个指针分别放在 nums1 有效元素的末尾m-1和 nums2 的末尾n-1写入指针放在 nums1 的末尾mn-1。每次比较两个指针指向的元素把较大的那个放到写入位置然后对应指针左移。因为写入位置永远在后面所以从后往前填充正好先用掉预留的空白区域不会覆盖还没有被比较过的数据。空间复杂度因此降到了 O(1)。我最早看到这个解法的时候第一反应是这方向有点反直觉。但仔细想一下就知道这里的核心逻辑和从前往后完全对称从前往后是每次找最小的放前面从后往前是每次找最大的放后面结果一样都是把整个数组合并成非递减序列。区别就在方向而方向正好避开了覆盖问题。2.4 三种解法复杂度对照解法核心思路时间复杂度空间复杂度代码量面试表现拼接后排序全量重排O((mn)log(mn))O(1)~O(mn)2行适合开场从前往后双指针临时数组 归并O(mn)O(m)约15行思路清晰从后往前双指针原地逆向归并O(mn)O(1)约10行最优解从表格里能看出来从后往前双指针在时间、空间、代码量三个维度都是最优的。这也是面试中最期望看到的答案。不过我不建议直接跳过前两种直接写最优解。因为面试官更看重的是你为什么会想到这里而不是你背了多少题解。能从暴力解法一步步推导到最优解这本身就是很强的信号。3. 最优解逐行拆解为什么从后往前写是安全的3.1 覆盖安全性背后的一小段推理从后往前写看似安全但真正理解它为什么安全才算把这道题吃透。先看指针初始值p1 m-1指向 nums1 最后一个有效元素p2 n-1指向 nums2 最后一个元素p mn-1指向整个 nums1 的最后一个位置也就是预留区的末尾。注意p 的初始位置比 p1 初始位置大 n这正是预留区的宽度。现在分两种情况看。如果一侧一直取 nums2 的元素那么 p2 最多可以贡献 n 次写入而每次写入位置从 mn-1 开始依次是 mn-1、mn-2、...、m总共 n 个位置恰好是预留区的全部位置。做完这 n 次nums2 必然被取空主循环结束此时 p 正好停在 m-1等于 p1 当前指向的位置但已经不需要再写入任何元素了。所以从 nums2 来的所有元素从头到尾都只填在预留区根本没有碰到 nums1 的有效数据。如果过程中取的是 nums1 的元素p1 会同步左移。因为每当 p1 左移一次p 也左移一次两者之间的差始终保持所以 p 不可能超过 p1。当 p1 不断左移它左侧的元素就越来越少而 p 始终在它右侧待着最终 p 追到 p1 右侧时说明 nums1 中所有有效元素已经全部处理完毕覆盖不覆盖已经没有影响。用更通俗的话说从后往前写写入的是已经比较过、确定是较大值的元素写入位置永远在还没处理的较小值区域的右侧。当 p 最终追到 p1 所在位置时意味着 nums1 中所有有效元素都已经参与过比较且被放入最终位置此时覆盖也不会造成任何损失。这个逻辑是自洽的也是面试时主动讲出来会很加分的点。3.2 完整代码与关键变量class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: # p1 指向 nums1 有效部分的最后一个元素 p1 m - 1 # p2 指向 nums2 的最后一个元素 p2 n - 1 # p 指向 nums1 合并后的最后一个位置 p m n - 1 # 只要两个数组都还有剩余元素就比较并放置较大值 while p1 0 and p2 0: if nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1 # 如果 nums2 还有剩余直接拷贝到 nums1 的前面 while p2 0: nums1[p] nums2[p2] p2 - 1 p - 1这段代码里有几个地方值得单独说明。第一比较符号用的是而不是。这意味着当 nums1[p1] 和 nums2[p2] 相等时我们取的是 nums2 的元素。结果依然正确因为相等的元素先后顺序不影响非递减有序性。如果你想保持稳定性即相同元素的相对顺序与原始数组一致取哪边都行但需要明确说明以避免歧义。第二最后一个 while 只处理 nums2 的剩余元素而没有处理 nums1 的剩余元素。这是因为 nums1 的剩余元素如果存在它们本身就待在最终该在的位置上不需要额外移动。而 nums2 的剩余元素如果存在说明 nums2 中这些元素比 nums1 中所有已处理的元素都小需要被一一填入 nums1 前端的空位。第三如果你把最后这个 while 条件改成while p1 0也能得到正确结果只是多做了无意义的赋值把 nums1 中的元素从后面挪到前面相同的位置。这在逻辑上没错但显得不够干净。3.3 边界情况在代码里如何体现当 m 0 时p1 -1主循环条件p1 0 and p2 0直接不成立进入最后的 while把 nums2 整个搬到 nums1。这个逻辑非常自然。当 n 0 时p2 -1两个循环都不会执行nums1 原样保留正确。当 m 0 且 n 0 时p -1n 0 使得最后一个 while 也不执行函数什么都不做。注意此时 p -1 只是一个初始化的整数不会真的去访问 nums1[-1]因为没有任何循环会进入。这也是我们不需要为这个 case 单独写特殊情况的原因。这几个边界情况代码写法上几乎不用额外判断就能天然处理。这也是最优解代码短小的一个原因边界情况被循环条件自然吞掉了。4. 边界条件与高频易错点4.1 四类典型输入的逐一分析虽然代码天然处理了边界但面试时考官可能直接给你一组特殊输入让你推演结果。我建议自己平时练习时把下面这些 case 跑一遍做到心中有数输入nums1 初始值mnums2n预期结果一般情况[1,2,3,0,0,0]3[2,5,6]3[1,2,2,3,5,6]nums1 为空[0,0,0]0[1,2,3]3[1,2,3]nums2 为空[1,2,3]3[]0[1,2,3]两者都为空[0]0[]0[0]有相等元素[1,2,3,0,0,0]3[1,2,3]3[1,1,2,2,3,3]所有 nums2 更小[4,5,6,0,0,0]3[1,2,3]3[1,2,3,4,5,6]所有 nums1 更小[1,2,3,0,0,0]3[4,5,6]3[1,2,3,4,5,6]一个个推演下来你会发现从后往前双指针几乎不会在这些 case 上翻车。真正翻车的地方往往在别处下面单独说。4.2 常见错误写法与排查思路我给别人 review 代码和自己刷题时见过不少典型错误挑几个出现频率高的说。第一个错误初始化 p 时写成了m而不是m n - 1。如果 p 初始值是 m意味着写入位置从预留区的第一个位置开始最后 nums1 的前半部分还是空的后半部分却堆着结果明显不对。我提醒自己记住一句话p 要指向 nums1 的最后一个位置而不是预留区的第一个位置。第二个错误比较时把条件写反把较大的值放到前面最后得到降序结果。虽然题目不允许但有人会干扰于从后往前取较大值这个说法把判断条件写反。建议写完代码后找一个简单 case比如 nums1[1,3,5,0,0,0]nums2[2,4,6]手动走一遍立刻就能发现方向对不对。第三个错误在最后处理剩余元素时把while p2 0写成while p1 0或者两个 while 都写。前者其实不影响正确性但后者会覆盖之前已经放置好的小元素结果错乱。如果你发现最终数组前半部分是乱的优先检查这个位置。第四个错误Python 里的负索引。如果 m0p1-1有人会在主循环条件之外不小心用nums1[p1]访问元素此时会取到数组最后一个元素而不是报错导致数据错乱很难排查。所以写 Python 代码时凡是涉及指针访问都要确保指针 0或者在进入循环前考虑边界。第五个错误用切片赋值时忘了nums1[:] ...而写成nums1 ...。LeetCode 的函数签名通常没有返回值如果你在函数内部重新绑定了 nums1 这个变量名函数外的 nums1 并不会改变提交就会失败。这是 Python 写原地算法题的一个经典坑不少人在其他题目上也踩过。提示写原地修改类题目第一步就是确认你是在修改传入的对象而不是给局部变量重新赋值。这一点在 Python 里尤其容易翻车。5. 从 LeetCode 88 延伸出去的算法地图5.1 归并排序 merge 步骤的简化版LeetCode 88 的解法本质上就是归并排序中 merge 函数的数组版。归并排序的整个流程是把数组分成左右两半递归排序左右两半然后调用 merge 把两个有序段合并。merge 函数做的事情和这道题一模一样两个有序子数组合并成一个有序数组。区别在于归并排序因为要合并的是同一个数组的两个部分如果原地合并需要非常精巧的内存管理实现复杂度高所以在实际工程和标准实现中通常直接使用 O(n) 的辅助数组。而 LeetCode 88 由于预先给 nums1 留了空间才能实现 O(1) 额外空间的原地合并。理解了这道题再去看归并排序的实现你会觉得 merge 部分特别眼熟。另外值得一提的是归并排序是稳定排序而 LeetCode 88 的标准解法中我们使用而不是保证了相等元素中 nums2 的排在 nums1 的后面从结果上看依然稳定。如果面试时聊到归并排序的稳定性可以把这个细节作为论据。5.2 合并两个有序链表换个数据结构再看同一道题对应 LeetCode 21合并两个有序链表。这道题和 88 在思路上高度一致都是两个有序序列合并每次取较小者放入结果。不同的是链表不需要考虑覆盖问题只需要修改 next 指针所以实现更为直接通常使用递归或迭代两种写法。链表版的迭代写法里你会用一个哨兵节点作为结果链表的头节点然后用一个 tail 指针依次连接较小的节点。这个哨兵技巧在处理链表合并时非常有用能省去大量对空链表和头节点的特殊判断。如果你已经练过 88再去做 21会发现核心思维模型是同一个两路有序流合并。反过来如果你先在链表上理解了哨兵和指针移动再回头处理数组版你会意识到数组版的核心难点不在指针移动而在往哪里写和会不会覆盖。两种数据结构各有一个独特难点结合起来理解整个知识结构会更立体。5.3 多路归并与外部排序两个有序数组合并能扩展到 k 个有序数组合并这就是多路归并。经典的实现方式是维护一个大小为 k 的小顶堆堆里存储每个数组当前的最小元素附带数组编号和元素索引。每次取出堆顶放入结果然后把该数组的下一个元素入堆。时间复杂度是 O(n*k log k)其中 n 是每个数组的平均长度。多路归并在工程上的最典型应用是外部排序。当待排序数据远超内存容量排序算法无法一次性 Load 进内存时会把大文件切分成多个小片段每个片段内部排序后写到磁盘然后通过多路归并把这些有序片段合并成整个有序文件。归并的路数 k 受限于内存大小因为需要同时维护 k 个输入缓冲区和 1 个输出缓冲区。我在读一些大数据处理框架源码时发现里面的外部排序模块核心逻辑就是这种多路归并只不过把数组换成了磁盘文件块把指针换成了文件读位置。所以说LeetCode 88 这种基础题真的不是刷完就扔的它在算法体系里的位置比表面看起来重要得多。5.4 工程场景有序数据流合并如果你觉得外部排序太远我再给一个更贴近日常开发的例子。假设有两个接口分别返回按创建时间排序的订单列表前端需要把它们合并展示在同一个时间线上。如果数据量不大可以直接把两个列表拼起来排序这正是暴力解法。但如果数据量很大需要分页拉取你就必须做两路归并每次从两个列表的当前游标处取较小的一条再决定从哪个接口拉下一页。这个模式在消息推送、日志汇总、商品推荐等场景里都能看到。两个有序数据流合并成一个有序数据流既要保证全局有序又要尽量少的 IO 次数这几乎就是把 LeetCode 88 的解法从数组换成了游标。我实际编码时会专门写一个合并两个有序数据流的工具函数把比较、推进、终止三个逻辑封装好用起来非常顺手。所以给一段真实体会算法题的练习价值并不一定在于它直接出现在你日常代码里而在于它训练的模式会在某个意想不到的地方帮到你。LeetCode 88 这种题就是典型的基础模式。6. 面试实践与每日练习方法论6.1 面对面试官时怎么展示思路如果面试官当面出这道题我不建议张口就直接背最优解。更稳的做法是分四步走。第一步先用自己的话复述一遍题目确认几个关键信息nums1 有效长度是 m总长度是 mn两个数组都是非递减排序合并结果必须写在 nums1 里函数没有返回值。复述的过程既是展示理解也是给自己争取思考时间。第二步给出暴力解法并分析复杂度。说我可以先把 nums2 拼到 nums1 尾部然后整体排序时间复杂度 O((mn)log(mn))。第三步顺着有序这个关键信息提出双指针。先讲从前往后版本指出它需要一个临时数组因为原地写会覆盖未处理数据。然后用既然 nums1 后面有 n 个空位我们可以从后往前写引出最优解。第四步把代码写出来并主动解释最后一个 while 为什么只处理 nums2。这个自然的思路演进比直接写出最优解更能体现算法素养。6.2 用五步法把一道题吃透我个人练习算法题时不喜欢单纯堆数量而是用一个五步法把每道题的价值榨干独立思考 15 分钟画出思路草图哪怕只能写出暴力解法。看题解或官方解答理解最优解为什么成立不放过任何细节。合上题解独立实现一遍遇到卡顿就标记下来。把这道题的不同解法都写一遍并对比复杂度和适用场景。在自己的练习笔记里给这道题写一页纸笔记包括题目出处、考点、解法对比、一个易错点、一个工程关联。LeetCode 88 用这个方法过一遍收获会远超AC 了三个字。特别是第五步一页纸笔记会让你在几周后再回看时用几分钟就能激活全部记忆。6.3 延伸变式想深一层题就活了LeetCode 88 最常见的变式有三个练完原题后可以顺手做做。变式一合并后去重。要求输出一个不含重复元素的有序数组这就需要在归并过程中比较相等元素时跳过重复值。核心还是在双指针基础上加一个去重判断。变式二两个数组都是降序排列。那么双指针方向就要反过来或者把它翻转成升序问题。变式三nums2 的数据不是一次性给全而是流式读取。这种情况下你没法提前知道 n 和 nums1 的总长度只能动态扩容。从后往前双指针就不能直接用因为初始的 p 位置不确定需要先确认扩容后的末位置。这实际上是工程里更常见的情况——数据是源源不断到达的而不是事先全部就位。每一个变式都在强化同一个核心模式两个有序序列合并的关键是控制好游标和写入位置避免数据被提前覆盖。想深一层这道题就不再是背答案的问题而是变成一个你可以举一反三的思维模型。我在实际练习里发现LeetCode 88 这道题有一个很容易被忽略的教育价值它教会我如果正向思维走不通试着从反向多看几眼。空位在哪里就从哪里开始填这句话听起来简单但用起来极其普遍。处理字符串压缩时要考虑从后往前构建结果链表反转时可以迭代也可以递归数组右移时需要考虑原地轮转的顺序这些问题的突破口都藏在方向的选择上。如果你正在做每日算法练习我建议不要急着追求刷题数量把这一道题真正吃透比刷十道简单题更划算。等到某天你在工程里遇到两个有序数据流合并的需求你会感谢自己当年没有跳过这道简单题。