LeetCode 88 合并两个有序数组Merge Sorted Array四种解法与原地合并技巧全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于本仓库 articles/merge-sorted-array.md 的核心讲解围绕 LeetCode 88 题「合并两个有序数组」展开覆盖前置知识、四种解法排序法、辅助空间归并、双指针原地归并 I/II的思路、算法步骤、多语言代码、复杂度对比以及常见陷阱。读者读完可以掌握从暴力解法到 O(mn) 时间、O(1) 空间的原地合并技巧并理解归并排序归并阶段在本问题中的直接应用。题目回顾与前置知识问题描述给定两个按非递减顺序排列的整数数组nums1和nums2以及两个整数m和n分别表示nums1和nums2中实际元素的数量。需要将nums2合并到nums1中使合并后的nums1同样按非递减顺序排列。关键约束是nums1的初始长度为m n其中前m个元素是有效数据后n个位置被 0 占位专门用于容纳nums2的元素。函数的返回值类型是void即要求原地修改nums1不能返回新数组。前置知识本仓库文档 merge-sorted-array.md 明确指出动手前应当熟悉以下三个基础概念数组Arrays理解如何按下标访问和修改元素例如nums1[i] x。双指针Two Pointers能够同时从不同方向遍历数组。本问题的所有高效解法都建立在这一技巧之上。原地算法In-place Algorithms在不额外分配线性空间的前提下修改数据结构。方法一排序法最直接的暴力思路思路既然nums1末尾预留了n个空位最朴素的做法就是把nums2的全部n个元素复制到nums1中下标m开始的位置然后对整个nums1排序。排序完成后合并结果自然就是有序的。算法步骤将nums2的n个元素复制到nums1起始下标为m。原地排序nums1。多语言实现Python 利用切片直接完成复制class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: nums1[m:] nums2[:n] nums1.sort()Java、C、JavaScript 等语言则通过循环逐元素复制后调用内建排序public class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { for (int i 0; i n; i) { nums1[i m] nums2[i]; } Arrays.sort(nums1); } }class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { for (int i 0; i n; i) { nums1[i m] nums2[i]; } sort(nums1.begin(), nums1.end()); } };class Solution { merge(nums1, m, nums2, n) { for (let i 0; i n; i) { nums1[i m] nums2[i]; } nums1.sort((a, b) a - b); } }注意 JavaScript 中Array.prototype.sort()默认按字典序排序必须传入(a, b) a - b比较函数才能按数值升序排列这是一个很容易踩的坑。Go 版本同样通过循环复制后调用sort.Intsfunc merge(nums1 []int, m int, nums2 []int, n int) { for i : 0; i n; i { nums1[im] nums2[i] } sort.Ints(nums1) }其余语言C#、Kotlin、Swift、Rust实现思路完全一致均可在原文档的对应标签页中查看完整代码。复杂度分析时间复杂度$O((m n) \log (m n))$瓶颈是排序。空间复杂度$O(1)$ 或 $O(m n)$取决于所选排序算法的实现例如 Python 的 Timsort、Java 的Arrays.sort可能使用额外缓冲区。其中 $m$、$n$ 分别表示nums1与nums2中的元素个数。方法二三指针 辅助空间标准归并思路两个数组都已经有序因此可以套用归并排序中“归并”阶段的经典做法在线性时间内完成合并。但直接从头向nums1写入会覆盖掉尚未处理的元素所以需要先把nums1的前m个元素复制到临时数组中再从两个“源”向nums1归并。算法步骤复制nums1的前m个元素到临时数组。使用三个指针i指向nums1的副本j指向nums2idx指向nums1的写入位置。比较两个源指针指向的元素将较小者写入nums1[idx]。递增对应的源指针与idx。持续执行直到两个源的所有元素都被放置完毕。多语言实现class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: nums1_copy nums1[:m] idx 0 i j 0 while idx m n: if j n or (i m and nums1_copy[i] nums2[j]): nums1[idx] nums1_copy[i] i 1 else: nums1[idx] nums2[j] j 1 idx 1Java 版本使用Arrays.copyOf复制前缀public class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] nums1Copy Arrays.copyOf(nums1, m); int idx 0, i 0, j 0; while (idx m n) { if (j n || (i m nums1Copy[i] nums2[j])) { nums1[idx] nums1Copy[i]; } else { nums1[idx] nums2[j]; } } } }C、JavaScript、C#、Go、Kotlin、Swift、Rust 的写法在结构上完全相同仅复制前缀的 API 不同如slice、copyOfRange、to_vec等完整代码见原文档。复杂度分析时间复杂度$O(m n)$每个元素恰好被比较和写入一次。空间复杂度$O(m)$用于存放nums1的副本。方法三三指针原地合并无额外空间—— 方案 I思路方法二需要 $O(m)$ 空间本质是因为从头归并会覆盖未处理数据。本方法的关键洞察是nums1尾部本来就有空位。如果从尾部向前填充就永远不会覆盖尚未处理的元素。每次比较两个数组当前最大的剩余元素把较大者放到nums1当前的末尾位置即可做到完全原地合并。算法步骤初始化last m n - 1即nums1的最后一个下标。当m 0且n 0时循环比较nums1[m - 1]与nums2[n - 1]。将较大值放入nums1[last]并递减对应的指针。递减last。若nums2仍有剩余元素把它们依次复制到nums1。多语言实现class Solution: def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) - None: last m n - 1 # Merge in reverse order while m 0 and n 0: if nums1[m - 1] nums2[n - 1]: nums1[last] nums1[m - 1] m - 1 else: nums1[last] nums2[n - 1] n - 1 last - 1 # Fill nums1 with leftover nums2 elements while n 0: nums1[last] nums2[n - 1] n - 1 last - 1C、JavaScript、C#、Go、Kotlin、Swift、Rust 版本逻辑一致注意 Rust 版将m n作为起始last并在每次循环开头递减是一种等价的写法细节。复杂度分析时间复杂度$O(m n)$。空间复杂度$O(1)$ 额外空间完全原地。方法四三指针原地合并无额外空间—— 方案 II推荐写法思路这是方法三更简洁的变体。观察可知一旦nums2的所有元素都放置完毕nums1剩余元素本来就位于正确位置无需再处理。因此只需在j 0时循环省去了独立的清理循环逻辑更清晰、更不易出错。算法步骤初始化指针i m - 1、j n - 1、last m n - 1。当j 0时循环若i 0且nums1[i] nums2[j]将nums1[i]放入nums1[last]递减i。否则将nums2[j]放入nums1[last]递减j。递减last。多语言实现class Solution: def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) - None: last m n - 1 i, j m - 1, n - 1 while j 0: if i 0 and nums1[i] nums2[j]: nums1[last] nums1[i] i - 1 else: nums1[last] nums2[j] j - 1 last - 1Java 版将三个自减操作压缩在一行非常紧凑public class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int last m n - 1; int i m - 1, j n - 1; while (j 0) { if (i 0 nums1[i] nums2[j]) { nums1[last--] nums1[i--]; } else { nums1[last--] nums2[j--]; } } } }复杂度分析时间复杂度$O(m n)$。空间复杂度$O(1)$ 额外空间。仓库源码印证各语言实际实现对比本仓库为本题提供了 11 种语言的实现与文档讲解相互印证。其中 python/0088-merge-sorted-array.py 采用方法三的变体用m n - 1动态计算写入位置并在主循环结束后用切片nums1[:n] nums2[:n]一次性补齐nums2的剩余元素简洁且高效class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) - None: while m 0 and n 0: if nums1[m-1] nums2[n-1]: nums1[mn-1] nums1[m-1] m - 1 else: nums1[mn-1] nums2[n-1] n - 1 if n 0: nums1[:n] nums2[:n]go/0088-merge-sorted-array.go 在文件头部显式标注了Time Complexity: O(m n)与Space Complexity: O(1)实现即为文档中的反向三指针方案func merge(nums1 []int, m int, nums2 []int, n int) { last : m n - 1 m - 1 n - 1 for m 0 n 0 { if nums1[m] nums2[n] { nums1[last] nums1[m] m - 1 } else { nums1[last] nums2[n] n - 1 } last - 1 } for n 0 { nums1[last] nums2[n] last - 1 n - 1 } }java/0088-merge-sorted-array.java 采用“读写指针”风格用for循环统一处理三种情况两数组都非空、仅剩nums1、仅剩nums2逻辑等价于文档中的方案 IIclass Solution { // Time: O(mn) | Space: O(1) public void merge(int[] nums1, int m, int[] nums2, int n) { int r1 m-1; int r2 n-1; for(int w mn-1; w 0; w--) { if(r1 0 r2 0) { nums1[w] nums1[r1] nums2[r2] ? nums1[r1--] : nums2[r2--]; } else if (r1 0) { nums1[w] nums1[r1--]; } else { nums1[w] nums2[r2--]; } } } }typescript/0088-merge-sorted-array.ts 与 rust/0088-merge-sorted-array.rs、kotlin/0088-merge-sorted-array.kt 均为标准的反向双指针写法c/0088-merge-sorted-array.c 则用i j 1等价计算写入位置并利用“nums1剩余元素已在正确位置”的性质提前return同样标注了Space: O(1)、Time: O(nm)。可以观察到尽管各语言代码风格各异但“从尾部向前归并、较大者先落位”的核心思想完全一致这也印证了方法三、四是本题的主流最优解。完整的 11 语言覆盖情况见仓库 README.md 中的完成度表格。常见陷阱Common Pitfalls陷阱一从前往后合并覆盖未处理数据原地合并时如果从nums1头部开始写入会覆盖尚未参与比较的元素从而破坏数据。务必从nums1尾部预留空位处向前合并先放置较大的元素——这正是方法三、四的设计出发点。陷阱二忘记复制nums2的剩余元素主归并循环结束后如果nums2中还有剩余元素必须显式复制到nums1中。nums1剩余的元素已经在正确位置但nums2剩余的元素需要额外放置遗漏该步骤会导致结果不完整例如m 0或n m的场景。方法四通过只循环j 0天然规避了这一陷阱。其他注意点边界条件当m 0时结果应直接等于nums2当n 0时nums1无需任何改动可直接返回。方法三、四的反向归并天然兼容这两种情况。相等元素处理归并条件中使用或不会影响最终结果的有序性但在方案 II 的i 0 nums1[i] nums2[j]写法中相等时优先取nums2元素、让j递减能确保循环必然终止且结果稳定有序。四种解法复杂度总览与选型建议方法核心思想时间复杂度空间复杂度适用场景方法一排序法复制 内建排序$O((mn)\log(mn))$$O(1)$ 或 $O(mn)$代码量最少笔试保底写法方法二辅助空间归并复制前缀 标准归并$O(mn)$$O(m)$便于理解归并过程面试讲思路用方法三原地归并 I反向三指针 清理循环$O(mn)$$O(1)$通用、直观教学首选方法四原地归并 II反向三指针 仅循环j$O(mn)$$O(1)$代码最简洁面试推荐在实际面试与工程中方法四是推荐写法它保留了原地、线性时间的全部优点同时代码最短、边界最少配合本仓库 python/0088-merge-sorted-array.py、go/0088-merge-sorted-array.go 等实现可以对照练习不同语言的写法差异。掌握本题的反向归并思想后还能顺带理解归并排序、有序数组合并等一系列同族问题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考