合并两个有序数组（LeetCode 88）

https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

1. 题目背景

你有两个已经排好序的数组：

nums1：前面是有效数字，后面是空位（0 占位），用来放另一个数组的元素。
nums2：完整的、也是排好序的数组。

目标是把 nums2 的元素合并到 nums1 中，并且 最终 nums1 还是升序。

例子

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3

前 3 个数 [1, 2, 3] 是有效的，后面 3 个 0 是空位。
要把 [2, 5, 6] 填进去，最终得到：

[1, 2, 2, 3, 5, 6]

2. 常见但低效的解法

有些同学会这样做：

把 nums2 直接加到 nums1 的后面。
调用 .sort() 排序。

虽然能跑通，但时间复杂度是 O((m+n) log(m+n))，不够快。
面试官通常会追问：能不能 O(m+n) 时间完成？

3. 高效解法——从尾巴开始合并

关键思路

因为两个数组都是升序的，我们可以用 双指针 从尾部往前填空位。

这样有两个好处：

不会覆盖掉还没处理的数字。
不需要移动数组中已有的元素。

三个指针的定义

p1 = m - 1 → 指向 nums1 有效部分的最后一个元素。
p2 = n - 1 → 指向 nums2 的最后一个元素。
p = m + n - 1 → 指向 nums1 的最后一个位置（空位）。

合并过程（例子推演）

以 nums1 = [1,2,3,0,0,0] 和 nums2 = [2,5,6] 为例：

步骤	p1指向	p2指向	比较	放到 p 位置	数组状态
1	3	6	6 大	放 6	[1,2,3,0,0,6]
2	3	5	5 大	放 5	[1,2,3,0,5,6]
3	3	2	3 大	放 3	[1,2,3,3,5,6]
4	2	2	一样大，放 nums2 的 2	[1,2,2,3,5,6]
结束	p2 < 0				完成

4. 为什么要 `p1 >= 0` 判断？

如果 nums1 的有效部分先用完（p1 < 0），那就不能再访问 nums1[p1]，否则会越界（尤其在 C++ 里直接崩溃）。
所以我们要保护一下：

if p1 >= 0 and nums1[p1] > nums2[p2]:...
else:...

5. Python 实现

def merge(nums1, m, nums2, n):p1 = m - 1p2 = n - 1p = m + n - 1while p2 >= 0:if p1 >= 0 and nums1[p1] > nums2[p2]:nums1[p] = nums1[p1]p1 -= 1else:nums1[p] = nums2[p2]p2 -= 1p -= 1

6. C++ 实现

#include <vector>
using namespace std;void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int p1 = m - 1;int p2 = n - 1;int p = m + n - 1;while (p2 >= 0) {if (p1 >= 0 && nums1[p1] > nums2[p2]) {nums1[p] = nums1[p1];p1--;} else {nums1[p] = nums2[p2];p2--;}p--;}
}