合并两个有序数组
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。
示例 1
示例 2
示例 3
m = 0 时 nums1 有效段为空，尾部占位 0 可忽略，直接把 nums2 写入即可。模拟答题者思考
1. 我先写暴力：把 nums1 前 m 个与整个 nums2 拷到新数组，排序后再写回 nums1——正确但多 O(m+n) 空间，也没利用「nums1 尾部有占位」这一条件。
2. 重复在哪里？若从头部像合并链表一样双指针写入 nums1，后移元素会覆盖还没读到的值；关键约束是只能原地，且尾部 n 个位置本来就是空的。
3. 倒着填：用 write 从 m+n-1 向左，每次在 nums1[p1] 与 nums2[p2] 中取较大者放到 nums1[write]。从尾部写不会踩到还没处理的 nums1 有效段（被写走的元素已经「归档」到更右侧）。
4. 当 p2 < 0 时 nums2 已全部写入；nums1 剩余未动的前缀本身已有序且已在正确位置，无需再移动。若 p1 先耗尽，则持续把 nums2 剩余段写入即可。
5. 每个元素最多被比较、写入一次，时间 O(m+n)；仅用三个下标，额外空间 O(1)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
p1 | int | 定义：nums1 有效段（前 m 个）中「尚未写入结果」的最大下标维护：初始为 m - 1，随较大元素从尾部落位而左移更新：当 nums1[p1] 被写到 write 后 p1 -= 1 |
p2 | int | 定义：nums2 中尚未合并的最大下标维护：初始为 n - 1，与 p1 比较谁更大更新：当 nums2[p2] 写入结果后 p2 -= 1；循环以 p2 >= 0 为条件（nums2 全部落位即结束） |
write | int | 定义：nums1 中下一个应写入「当前最大元素」的下标维护：从 m + n - 1 向左填，保证尚未处理的尾部始终是空闲或可被覆盖的占位更新：每写入一个数后 write -= 1 |
落码步骤
1. p1 = m - 1，p2 = n - 1，write = m + n - 1
2. 当 p2 >= 0：若 p1 >= 0 且 nums1[p1] > nums2[p2]，则 nums1[write] = nums1[p1] 并 p1--；否则 nums1[write] = nums2[p2] 并 p2--；然后 write--
3. 循环结束即完成（p2 耗尽时 nums1 左侧剩余元素已在位；无需返回值）
代码实现
class Solution:
def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
p1, p2, write = m - 1, n - 1, m + n - 1
while p2 >= 0:
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]
p1 -= 1
else:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, write = m + n - 1;
while (p2 >= 0) {
if (p1 >= 0 && nums1[p1] > nums2[p2]) {
nums1[write] = nums1[p1--];
} else {
nums1[write] = nums2[p2--];
}
--write;
}
}
};
// 时间 O(m+n)，空间 O(1)复杂度分析
O(m + n)
O(1)
常见坑
从数组头部合并并原地写入：会覆盖 nums1 里尚未参与比较的元素，除非先整体后移 O(m) 次。
比较时忘记 p1 >= 0：m = 0 时仍访问 nums1[p1] 会越界；p1 耗尽后应只从 nums2 继续填。
把 nums1 尾部占位 0 当成有效元素参与 m 计数——有效长度只看 m，不是 len(nums1)。
必测边界 Case
nums1 = [1], m = 1, nums2 = [], n = 0 → [1]（循环不进入）
nums1 = [0], m = 0, nums2 = [1], n = 1 → [1]
nums1 = [4,5,6,0,0,0], m = 3, nums2 = [1,2,3], n = 3 → [1,2,3,4,5,6]（先填较大者，最终左侧小段自动就位）