京公网安备11010502063487号给定两个升序数组 nums1 和 nums2，把 nums2 合并进 nums1，合并后 nums1 仍然有序。nums1 的长度是 m + n，前 m 个是有效元素，后面 n 个位置是 0 占位，正好留给 nums2 的元素。因为要求原地合并、不返回新数组，直接从前往后合并会覆盖 nums1 里还没读到的元素。技巧是从后往前合并：三个指针，i 指向 nums1 有效部分的末尾，j 指向 nums2 的末尾，k 指向要写入的位置（nums1 的最后一个空位）；每次把两个数里较大的写到 k。本文用真实数据展示从前往后合并会错多少，给出五种语言的实现，并把从后往前的过程做成分步演示。
完整题目见官方页面（链接在文末）。基准解是把 nums1 的有效部分和 nums2 拼起来直接排序，与从后往前的双指针是两种独立的写法。一共 12 组用例，覆盖：官方三个示例、nums2 为空、nums1 有效部分为空、nums2 的元素全部更大或全部更小、含重复值和负数：
输入 [[1,2,3,0,0,0],3,[2,5,6],3] 输出 [1,2,2,3,5,6] 输入 [[1],1,[],0] 输出 [1] 输入 [[0],0,[1],1] 输出 [1] 输入 [[2,0],1,[1],1] 输出 [1,2] 输入 [[4,5,6,0,0,0],3,[1,2,3],3] 输出 [1,2,3,4,5,6] 输入 [[1,2,3,0,0,0],3,[4,5,6],3] 输出 [1,2,3,4,5,6]
自然的想法是像合并两个链表那样，从最小的元素开始往前合并。但这里合并的结果要写回 nums1 自己，从前往后写的时候，写入位置会追上 nums1 还没读到的元素，把它们覆盖掉。下面是从前往后、直接写进 nums1 的写法与 solve 的真实结果：
# 从前往后、直接写进 nums1 的写法（会覆盖还没读到的元素） nums1=[1, 2, 3, 0, 0, 0], m=3, nums2=[2, 5, 6]: 从前往后 -> [1, 2, 2, 2, 5, 6] solve -> [1, 2, 2, 3, 5, 6] nums1=[4, 5, 6, 0, 0, 0], m=3, nums2=[1, 2, 3]: 从前往后 -> [1, 1, 1, 1, 2, 3] solve -> [1, 2, 3, 4, 5, 6] nums1=[2, 0], m=1, nums2=[1]: 从前往后 -> [1, 0] solve -> [1, 2] 随机 20000 组：该写法出错的有 13844 组（69.2%）
官方示例 [1, 2, 3, 0, 0, 0] 与 [2, 5, 6]：从前往后得到 [1, 2, 2, 2, 5, 6]，nums1 里的 3 被覆盖了，正确答案是 [1, 2, 2, 3, 5, 6]。第二组更严重：得到 [1, 1, 1, 1, 2, 3]，正确答案是 [1, 2, 3, 4, 5, 6]。在随机的 20000 组数据里，这种写法出错的有 13844 组，占 69.2%。从后往前写时，写入位置 k 始终在 i（nums1 还没读的最后一个元素）的右边或与之重合，所以不会覆盖还没读的元素。
i = m - 1，j = n - 1，k = m + n - 1。只要 nums2 还有元素（j >= 0）：如果 nums1 的有效部分还有元素并且 nums1[i] > nums2[j]，把 nums1[i] 写到 nums1[k]，i 减一；否则把 nums2[j] 写到 nums1[k]，j 减一；每次 k 减一。当 nums2 用完时循环结束：nums1 剩下的前面部分本来就有序，并且已经在正确的位置上，不需要再动。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums1, m, nums2, n): i, j, k = m - 1, n - 1, m + n - 1 # 三个指针都从后往前：i 指 nums1 有效部分的末尾，j 指 nums2 的末尾，k 是要写入的位置 while j >= 0: # nums2 用完了就结束：nums1 剩下的部分本来就在正确位置 if i >= 0 and nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1 return nums1
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,3,0,0,0],3,[2,5,6],3] → [1,2,2,3,5,6] [[1],1,[],0] → [1] [[0],0,[1],1] → [1] [[2,0],1,[1],1] → [1,2] [[4,5,6,0,0,0],3,[1,2,3],3] → [1,2,3,4,5,6] [[1,2,3,0,0,0],3,[4,5,6],3] → [1,2,3,4,5,6]
Java · 解法代码class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; // 三个指针都从后往前：i 指 nums1 有效部分的末尾，j 指 nums2 的末尾，k 是要写入的位置 while (j >= 0) { // nums2 用完了就结束：nums1 剩下的部分本来就在正确位置 if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--]; else nums1[k--] = nums2[j--]; } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,3,0,0,0],3,[2,5,6],3] → [1,2,2,3,5,6] [[1],1,[],0] → [1] [[0],0,[1],1] → [1] [[2,0],1,[1],1] → [1,2] [[4,5,6,0,0,0],3,[1,2,3],3] → [1,2,3,4,5,6] [[1,2,3,0,0,0],3,[4,5,6],3] → [1,2,3,4,5,6]
Go · 解法代码func merge(nums1 []int, m int, nums2 []int, n int) { i, j, k := m-1, n-1, m+n-1 // 三个指针都从后往前：i 指 nums1 有效部分的末尾，j 指 nums2 的末尾，k 是要写入的位置 for j >= 0 { // nums2 用完了就结束：nums1 剩下的部分本来就在正确位置 if i >= 0 && nums1[i] > nums2[j] { nums1[k] = nums1[i] i-- } else { nums1[k] = nums2[j] j-- } k-- } }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,3,0,0,0],3,[2,5,6],3] → [1,2,2,3,5,6] [[1],1,[],0] → [1] [[0],0,[1],1] → [1] [[2,0],1,[1],1] → [1,2] [[4,5,6,0,0,0],3,[1,2,3],3] → [1,2,3,4,5,6] [[1,2,3,0,0,0],3,[4,5,6],3] → [1,2,3,4,5,6]
JavaScript · 解法代码function merge(nums1, m, nums2, n) { let i = m - 1, j = n - 1, k = m + n - 1; // 三个指针都从后往前：i 指 nums1 有效部分的末尾，j 指 nums2 的末尾，k 是要写入的位置 while (j >= 0) { // nums2 用完了就结束：nums1 剩下的部分本来就在正确位置 if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--]; else nums1[k--] = nums2[j--]; } }
$ node run.js < cases.jsonl [[1,2,3,0,0,0],3,[2,5,6],3] → [1,2,2,3,5,6] [[1],1,[],0] → [1] [[0],0,[1],1] → [1] [[2,0],1,[1],1] → [1,2] [[4,5,6,0,0,0],3,[1,2,3],3] → [1,2,3,4,5,6] [[1,2,3,0,0,0],3,[4,5,6],3] → [1,2,3,4,5,6]
C++ · 解法代码#include <vector> using namespace std; class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; // 三个指针都从后往前：i 指 nums1 有效部分的末尾，j 指 nums2 的末尾，k 是要写入的位置 while (j >= 0) { // nums2 用完了就结束：nums1 剩下的部分本来就在正确位置 if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--]; else nums1[k--] = nums2[j--]; } } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,3,0,0,0],3,[2,5,6],3] → [1,2,2,3,5,6] [[1],1,[],0] → [1] [[0],0,[1],1] → [1] [[2,0],1,[1],1] → [1,2] [[4,5,6,0,0,0],3,[1,2,3],3] → [1,2,3,4,5,6] [[1,2,3,0,0,0],3,[4,5,6],3] → [1,2,3,4,5,6]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
两个数组各有 m = n 个元素，nums1 的偶数和 nums2 的奇数交错（这样两个指针交替前进），m = n 分别为 1 万、10 万、100 万，每个规模取三次中最快的一次：
m = n | 暴力解 | 本文解法
10000 | 0.170 ms | 0.935 ms
100000 | 1.990 ms | 9.603 ms
1000000 | 18.597 ms | 97.610 ms双指针合并是线性的：从 10 万到 100 万（10 倍）耗时增长约 10.2 倍。在 Python 里，"拼起来再 sorted"（基准）反而更快（100 万时 18.6ms 对 97.6ms），因为 sorted 是 C 实现，并且能识别出输入由两段已经有序的序列拼成，几乎是线性的。这个对比只能说明 Python 里 C 实现的排序更快，不能说明双指针的算法差：它的价值是原地、不需要额外的 O(m + n) 空间，而 sorted 版本会新建一个数组。
Python 版本另外和"拼起来再排序"做了随机对拍：两个各 0 到 7 个元素的有序数组（取值 -5 到 9，不同时为空）：
随机对拍 20000 组（两个各 0 到 7 个元素的有序数组（取值 -5 到 9，不同时为空）；nums1 后面补 n 个 0 作为空位），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例。从后往前：6（nums2）比 3 大，写到最后一位；5 比 3 大，写到倒数第二位；nums1 的 3 比 nums2 的 2 大，写到倒数第三位；然后 2 和 2 相等，取 nums2 的 2；nums2 用完，nums1 前面的 [1, 2] 已经在正确位置。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。