合并两个有序数组这道题在 LeetCode 上挂着 Easy 的标签但真到了面试现场它能淘汰的人远比想象中多。我印象很深有一次候选人把“先合并再排序”写出来然后理直气壮说这就是最优解我追问了一句“那如果 nums1 空间刚好只够呢”他愣了好一会儿。这个题目表面上是考数组操作本质上考的是双指针思维、原地操作的边界处理以及对时间复杂度的敏感度。今天我就把这题掰开揉碎从最暴力的做法讲到面试官最喜欢的原地双指针顺便把 Python 里那些能偷懒的内置工具也拿出来遛一遛。这篇文章不是单纯给你背答案而是把每种解法背后的“为什么”讲清楚。无论你是准备面试的算法新手还是写业务代码时想优雅地合并两个有序列表都能拿到可以直接抄作业的方案以及我在实际调试中踩过的那些坑。1. 先搞清楚题目在问什么1.1 题目描述和隐藏陷阱原题长这样给定两个有序整数数组 nums1 和 nums2把 nums2 合并到 nums1 中使最终结果仍然有序。这里有个关键约束nums1 的长度是 m n前 m 个位置放的是有效元素后面 n 个位置用 0 占位专门腾出来给 nums2 的元素用。这个“末尾补 0 占位”的设计是第一个陷阱。很多第一次做这道题的人一看是“合并”直接写nums1.sort()结果把末尾的 0 全排到前面去了。我见过不止一个人在这里翻车而且翻车之后还一脸茫然觉得 Python 的 sort 出了问题。第二个陷阱藏在“原地”这两个字里。题目要求把结果直接写进 nums1不允许你 new 一个全新的数组返回。这意味着你的解法必须考虑到 nums1 的容量是固定的你不能在中途让 nums1 的长度随意变化更不能用nums1 nums1 nums2这种重新赋值的招数——这会让 nums1 指向一个全新的对象并不是真正原地修改。1.2 面试官到底想考什么别看这题标着 Easy它一次性考了三个重要的算法基本功。第一个是双指针技术。两个有序数组合并本质上是把两个升序序列归并成一个升序序列这是归并排序的 merge 阶段。归并排序是分治思想的核心代表如果你连 merge 都不会写后面遇到链表归并排序、外部排序、多路归并基本就卡死了。第二个是边界条件处理。m 和 n 可能为 0数组可能很长元素可能全是重复的。这些边界情况在面试中就是送分题也是送命题。很多人主流程写得飞快一遇到空数组就报 IndexError这种失误在面试官眼里是很掉价的。第三个是空间复杂度优化。从“新建数组再合并”到“从后往前原地合并”空间复杂度从 O(m) 降到 O(1)。面试官追问“能不能不申请额外空间”的时候考的就是你有没有意识到从后往前操作可以避免覆盖问题。1.3 这题的通用价值比想象中大我在实际工作中被这个 merge 逻辑救过好几次。比如两个渠道各拉了一份用户列表都按注册时间排好序了要合并成一个去重后的列表用于全量推送再比如日志系统中多个分片的日志文件要按时间戳合并成一个大文件这就是典型的 merge 过程。还有数据库做归并连接Merge Join的时候本质上也是这种有序序列合并的扩展。所以说花时间把这题吃透不只是为了过面试它本身就是一个在工程里高频出现的基础操作。你把这题的边界情况和优化思路搞明白了后面遇到各种“合并有序”相关的问题都等于白捡。2. 方案一先合并再排序最直观但也最容易被追问2.1 代码确实能一行搞定先来看最简单的写法def merge(nums1, m, nums2, n): nums1[m:] nums2 nums1.sort()如果你只是要一个能跑的答案那就到这里为止了。nums1[m:] nums2是把 nums2 的所有元素覆盖到 nums1 从第 m 位开始的区间上也就是把那些占位的 0 替换成真正的数据。然后sort()把整个数组重新排序。这个解法能通过但隐藏了一个你必须要知道的细节nums1[m:] nums2是在原地修改 nums1 的切片所以赋值的长度不需要和原切片长度一样列表会自动调整大小。如果你的 nums1 长度恰好是 m n那么这个操作不会改变列表长度正好满足题目要求。2.2 为什么这种解法在面试里会被追问时间复杂度是 O((mn) log(mn))因为sort()是基于 Timsort 的最坏情况下需要这么多时间。空间复杂度取决于 sort 的具体实现Timsort 在最坏情况下会申请 O(n) 的额外空间虽然是 C 语言层面的内存不算我们代码里的显式空间但面试官较真的话这也能算一笔账。最关键的问题在于这个解法完全没有利用“两个数组已经各自有序”这个前提。你等于把两个有序数组先打乱成一个大杂烩再重新排序。理想情况下合并两个有序数组只需要一趟线性扫描时间复杂度是 O(mn)而你却用了一个 log 级别的排序这在数据量大的时候差距非常明显。举几个数字体感一下当 m1000、n1000 时O(mn) 只需要大约 2000 次比较而 O((mn)log(mn)) 需要 2000 * 11 等于 22000 次比较差了一个数量级。当数据量到了十万级别差距会更吓人。2.3 什么时候可以放心用如果面试官明确说“我不要求最优解你先把能跑的写出来”那先写这个方案是完全没问题的至少能证明你基本功扎实。但写完一定要主动说“这个方法时间复杂度是 O((mn)log(mn))没有利用数组有序的性质我可以优化到 O(mn)。” 这句话一出口面试官基本就放心了。在工作里如果合并的两个列表都不大比如总量几百条我也会偷懒用 sort 方案毕竟代码可读性最高维护成本最低。性能优化要分场景不是任何地方都值得上最优解。3. 方案二双指针法这道题的标准答案3.1 核心思想就是“谁小谁先走”双指针的思路非常朴素你面前有两排从小到大排列的士兵现在要把他们合并成一排你只需要两个手指头分别指在两排的第一个士兵身上。每次比较两个手指指向的士兵谁个子矮谁就先站到新队伍里然后让那排的指针往后挪一位。重复这个过程直到其中一排空了再把另一排剩下的人全部接上去。这个比喻涵盖了双指针解法的全部核心逻辑比较当前两个指针指向的元素把较小的放进结果数组然后移动对应指针。循环结束条件是两个指针中有任何一个越界最后做一次收尾把另一个数组剩余的元素全部拷进去。3.2 从前往后合并需要 O(m) 额外空间最容易想到的双指针版本是创建一个新数组来存结果但题目要求原地修改 nums1不能返回新数组所以这里有个折中策略先把 nums1 的有效部分复制一份出来然后在这份副本和 nums2 上进行双指针比较把结果写回 nums1。def merge(nums1, m, nums2, n): nums1_copy nums1[:m] i, j, k 0, 0, 0 while i m and j n: if nums1_copy[i] nums2[j]: nums1[k] nums1_copy[i] i 1 else: nums1[k] nums2[j] j 1 k 1 while i m: nums1[k] nums1_copy[i] i 1 k 1 while j n: nums1[k] nums2[j] j 1 k 1这里有个细节值得停下来想一下为什么要把 nums1 的有效部分先复制出去因为题目要求原地写回 nums1而 nums1 的前 m 个位置正在被我们当作结果区域使用。如果直接用 nums1 的前面部分来存结果当你从前面拿走一个 nums1 的元素时那个位置的原始值就被覆盖了后面还没被比较的 nums1 元素就丢了。复制副本的本质是用 O(m) 的空间换取不被覆盖的安全性。这段代码的时间复杂度是 O(mn)空间复杂度 O(m)。作为双指针入门它比后面的原地版本更容易理解尤其适合第一次接触归并思想的人。3.3 从后往前合并面试官最想看到的版本如果面试官追问“能不能不用额外空间”答案就是从后往前填。既然 nums1 后面有 n 个空位那我们就从最后一个位置开始往前写每次都取两个数组当前剩余元素中的较大者放到结果数组的末尾。这样可以保证已经写进去的元素不会覆盖掉还没读取的 nums1 元素。def merge(nums1, m, nums2, n): p1 m - 1 p2 n - 1 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 nums1[:p2 1] nums2[:p2 1]最后一行是很多人容易漏掉的关键如果 nums2 还有剩余元素直接把 nums2 开头的那些元素覆盖到 nums1 开头。为什么因为 nums1 开头的元素要么已经被正确地放到后面去了要么就是和 nums2 剩余元素比较后留下的较大值此时 nums1 开头的空闲位置正好放 nums2 剩下的较小值。这个收尾操作的时间复杂度是 O(1) 的量级切片赋值按位置逐个写入实际是 O(p21)但确实把代码的边界处理补全了。如果反过来nums1 还有剩余元素就不需要特殊处理了因为它们本来就在 nums1 前面的位置而且是这一轮比较中的较小值留在原地就是正确的。很多人第一次写在这里会犯迷糊要么多写一个 while p1 0 的循环要么不知道怎么处理 p2。多写一个循环也不算错只是不够简洁。3.4 两种双指针方案怎么选从前往后版本需要 O(m) 额外空间从后往前版本是 O(1) 额外空间两者时间复杂度都是 O(mn)。面试的时候我的建议是先把从前往后版本的思路讲清楚让面试官看到你理解了双指针的核心逻辑再主动补充一句“其实还可以从后往前把空间复杂度降到 O(1)”然后直接写出原地版本。写的时候还要注意一个比较运算符的细节在内层 if 判断里用还是会影响相同元素的来源顺序。用则当 nums1[p1] 和 nums2[p2] 相等时取 nums2 的元素等于把相同元素的相对顺序颠倒了用才会让考验相对顺序的合并保持稳定。严谨的工程场景下稳定性很重要但面试时更关键的是你要意识到这个问题存在并且能说出你选某个符号的理由。4. 方案三Python 内置工具到底能不能用4.1 heapq.merge 合并迭代器Python 的 heapq 模块里藏着一个 merge 函数专门用来合并多个有序序列。它的效果和双指针 merge 一致但返回的是一个迭代器非常省内存。from heapq import merge def merge_with_heapq(nums1, m, nums2, n): nums1[:] list(merge(nums1[:m], nums2))这行代码的步骤是先取 nums1 前 m 个元素作为迭代器和 nums2 一起传给 merge得到一个新的迭代器然后转成列表用切片赋值的方式写回 nums1。必须说明的是merge内部用的是堆结构一次只从两个迭代器里取元素空间占用很小但当你list()把它消耗完时内存占用就是 O(mn)。所以从空间复杂度看它和直接新建数组没有本质区别。另外切片赋值nums1[:]要求右边序列长度和 nums1 长度一致否则会改变列表长度在这个题目场景里正好一致所以能用。如果 nums1 长度不是 mn 而是更多这个写法还需要调整为nums1[:mn] ...。这个方案我一般只在工程里合并两个迭代器流时用面试时不推荐当作主答案因为面试官大概率没听过 heapq.merge你还得解释一堆不如从后往前双指针来得干净。4.2 bisect.insort 逐个插入如果你要合并的数组不太长也可以用二分查找定位插入点然后逐一把 nums2 的元素插进 nums1import bisect def merge_with_insort(nums1, m, nums2, n): nums1[:] nums1[:m] for x in nums2: bisect.insort(nums1, x)这里先把 nums1 的前 m 个有效元素单独提出来因为不处理掉的话后面的 0 也会参与二分查找插入位置会错。然后每进来一个元素insort 会找到它应该插入的下标并把后续元素整体后移。这个方案的时间复杂度是 O(n * m)因为每次插入都是 O(m) 的线性移动n 个元素就是 O(n*m)。数组规模小比如两个长度都不到 100用起来完全没问题代码简洁可读性很高。但面试时千万别拿这个当最优解会被追问到怀疑人生。4.3 用 Timsort 的特性能不能偷懒前面说过直接nums1[m:] nums2; nums1.sort()是 O((mn)log(mn))。但因为 Python 的 sort 是 Timsort它专门优化了“部分有序”的情况所以当两个子数组都是有序的时实际运行时间可能会接近 O(mn)。理论上最坏复杂度还是 O((mn)log(mn))但如果你只用一句“实测很快”来论证在面试里站不住脚。不过有意思的是Timsort 的有序性检测确实能识别出“前半段有序、后半段有序”的结构。我在本地用长度为 10000 的两个随机有序数组测试过nums1[m:] nums2; nums1.sort()和双指针原地 merge 的耗时差距在十几毫秒的量级感知不强。但在面试里你要跟面试官讲清楚的是理论复杂度而不是跑个 benchmark 来抬杠。4.4 方案选择建议如果让我给一个直接的结论工程里数据量小且追求可读性直接用nums1[m:] nums2; nums1.sort()。工程里数据量较大但内存充足用heapq.merge或者自己写的双指针版本。面试里第一反应写双指针追问空间复杂度时写从后往前版本。如果面试官不排斥你用内置库也可以提一句 heapq.merge作为加分项展示你对标准库的熟悉程度。5. 变式题目和真实场景扩展5.1 合并 K 个有序数组面试中这道题经常被扩展成现在有 K 个有序数组怎么合并成一个有序数组你的第一反应可能是两两合并但合并 K 次的复杂度是 O(K * N)因为每合并一次数据规模都在变大。更优的做法是使用最小堆先把每个数组的第一个元素放进堆里然后每次弹出最小值再从这个最小值所在数组的下一个位置取元素入堆。这样总时间复杂度是 O(N log K)堆的大小始终是 K。这在工程上就是经典的“多路归并”搜索引擎索引构建、大数据排序的外部归并阶段都在用这个思路。如果你面试时能把这道题从两路扩展到 K 路顺带讲清楚堆的作用面试官对你这题的印象分直接拉满。5.2 合并后找中位数另一个热门变式是 LeetCode 第 4 题两个有序数组合并后的中位数。你要是真把两个数组合并再找中位数复杂度是 O(mn)虽然能过但最优解要求 O(log(min(m,n)))。做法是利用二分查找在两个数组的交错位置上找到一个切分点使得左半部分的最大值小于右半部分的最小值。这个思路更考验对有序数组性质和二分查找的理解也是从“合并有序数组”延伸出来的经典进阶题。如果你刚把这题的基础版吃透我建议顺手刷一下第 4 题。它们共享同一个直觉有序数组的归并、切分和中位数本质上是同一个主题下的不同问法。5.3 真实工程日志合并与用户列表合并说回实际工作。有一次我做数据迁移要从两张历史表里导用户 ID两张表都按 ID 递增排好序目的是合并成一个文件给下游去重后全量处理。数据量大概是千万级别用 SQL 里的UNION等于是先合再排序数据库压力大得吓人。我直接用双指针合并两个有序文件流一边读一边写内存占用稳定在几 MB跑完大概十分钟。那次经历让我对 merge 这个操作的实用价值印象极深。另一个场景是日志系统。每个服务节点会生成局部有序的日志文件需要按时间戳合并成全局有序的日志流做问题排查。这种场景你不可能把所有日志都读进内存再排序必须用迭代器或者流式 merge按行读取比较时间戳决定先输出哪一条。这就是heapq.merge的实际用武之地。5.4 稳定排序和相等元素处理的思考最后补充一个容易忽略的点合并有序序列时的稳定性。所谓稳定是指两个数组中如果出现相等的元素合并后它们的前后顺序是否和原数组一致。如果你在两个相等的元素之间倾向于保留 nums1 的元素在前那在用比较时需要小心。从前往后版本中if nums1_copy[i] nums2[j]会让 nums1 的相等元素先被取走如果写就是 nums2 的相等元素先被取走。两种写法都不影响结果数组的有序性但面试官如果问到“合并过程会不会破坏相对顺序”你能意识到这个差异并给出选择理由会显得你考虑得很周全。6. 常见问题与避坑技巧实录6.1 高频报错和排查思路我在各种各样的教程群、内推群里看到过很多人贴自己写的合并有序数组代码出问题的地方高度一致。我把最常见的几类整理成一张表方便你对照排查。现象原因解决方案结果数组里出现 0把末尾占位的 0 当成有效元素直接 sort先对有效区间切片或先覆盖再排序IndexError: list assignment index out of range往 nums1 里写结果时下标越界通常是忘了 nums1 实际长度只有 m不是 mn确认参数含义使用 p m n - 1 这类指针时注意边界结果数组缺失部分元素双指针收尾阶段没处理完某个数组剩余元素补上 p1 或 p2 的收尾循环从后往前版本记得处理 nums2 剩余元素结果顺序错乱从前往后直接覆盖了还没读取的 nums1 元素先用 nums1_copy 保存有效部分或改用从后往前修改了 nums1 但外部看到的还是旧数组用nums1 ...重新赋值而不是切片或索引修改用nums1[:] ...或对下标元素逐个赋值6.2 边界条件逐条过一遍不管是自己写还是看别人代码我都会习惯性把下面这些边界条件在心里过一遍m 0说明 nums1 没有有效元素合并结果等于 nums2。从前往后版本会直接跳过第一个 while进入 nums2 的收尾循环从后往前版本会直接执行nums1[:p21] nums2[:p21]。n 0说明 nums2 是空数组结果等于 nums1 原本的样子。两个版本都会跳过第二轮逻辑代码不会报错。m 0 且 n 0两个数组都是空的合并结果还是空数组需要保证代码此时不越界。nums1 和 nums2 全部相等此时双指针会一直走 else 分支或者 if 分支取决于比较符号最终结果依然有序。nums1 的有效元素全部小于 nums2从后往前版本中 p2 走完后nums1 开头要覆盖的恰好是 nums2 的全部结果正确。nums2 的所有元素都小于 nums1 的有效元素从后往前版本中 p1 走完后nums2 剩余元素直接放到 nums1 最前面可以做到完全不额外申请内存。6.3 独家经验心得这里分享几个我反复踩过之后才养成的习惯。第一写双指针时永远先确定指针的含义。p1、p2、p 分别指什么初始值是什么循环条件是什么三个问题写下来贴在自己面前再动代码。很多错误都源于指针含义模糊。第二从后往前的版本中最后一行的切片赋值nums1[:p2 1] nums2[:p2 1]经常被忽略。我发现把这个写反成nums1[:p1 1] nums1[:p1 1]的人也有那等于什么都没做。一定要理解只有 nums2 剩余元素需要特殊处理nums1 剩余元素本来就在正确位置。第三用切片比较顺手但也会藏问题。nums1[:m]是复制出一个新列表不会影响原来的 nums1这是对的。但如果你写tmp nums1那不是复制只是给同一个列表起了个别名后面tmp被修改时nums1 也会跟着变很多人第一次写代码就在这里莫名奇妙地丢数据。第四检查代码时不要只盯着主循环也要把收尾循环和极端输入都跑一遍。有时候主循环写得完美结果收尾循环少写了k 1或者下标写错一调试就是半天。最后说个心态层面的东西。合并两个有序数组这道题看起来简单但它是很多算法思维的起点。你把它彻底吃透后面学归并排序、二分查找、堆、K 路归并都会有“原来还是这套东西”的豁然开朗感。别嫌这题简单能把简单题讲清楚、写干净、边界考虑全本身就比会背一堆模板的人强得多。我自己后来面试别人的时候也特别喜欢拿这题当开场。不是因为想刁难人而是从一道 easy 题里就能看出一个人是背了答案还是真正理解了算法。你写代码前有没有先和面试官确认输入输出的含义你写完后会不会主动补边界用例你在被追问空间复杂度时是直接懵掉还是快速切换思路这些才是这题真正的价值所在。