LeetCode 面试题 10.01. 合并排序的数组
目录
题目描述
题意分析
两个升序数组 A、B，其中 A 的实际长度是 m + n，但只有前 m 个位置装着有效数据，后 n 个是预留的空位。要求把 B 的 n 个元素合并进 A，使 A 整体保持升序。函数没有返回值，说明必须原地修改 A，不能构造新数组再返回。
「A 末尾预留了恰好 n 个空位」是题目最重要的暗示。出题人特意把数组开大而不是只给 m 个元素，就是在提示：合并结果的总容量已经确定，最终每个位置放什么也是确定的，可以直接往目标位置写。
两个数组都已有序，这个条件意味着不需要任何排序或查找——每一步只要比较两个数组当前的候选元素，就能确定谁该占据下一个位置。这是线性合并成立的全部依据。
边界上要考虑：m 可以为 0，此时 A 全是空位，等价于把 B 整体复制过去；n 可以为 0，此时什么都不用做；两个数组可能有大量相等元素，比较时要保证不丢不重；B 的元素可能全部小于 A 的最小值，也可能全部大于 A 的最大值，这两种极端情况会分别耗尽某一侧的指针。
解法：从后向前合并
核心思路
两个数组已经升序，当前未合并元素中的最大值一定是
A[i]与B[j]中较大的那个。若从前往后写入 A，会覆盖 A 中尚未读取的有效元素；而 A 的空位都在尾部，所以从后往前填充可以原地完成合并。令
i = m - 1、j = n - 1分别指向两组未处理元素的末尾，k = m + n - 1指向下一个写入位置。循环维护两个不变量：
A[k+1..m+n-1]已经是最终答案中最大的那一段，且顺序正确。- 当 B 还有元素时，
k - i = j + 1 > 0，所以写入位置始终在 A 的未读位置右侧，不会覆盖A[i]。每轮把较大的候选写入
A[k]，相应读指针与k同时左移。不需要等待 A 全部耗尽：一旦 B 已经写完，A 剩余元素原本就在正确的前缀中；若 A 先耗尽，则继续把 B 写入即可。正确性说明：当 A、B 都有剩余元素时，根据升序性质，
A[i]与B[j]的较大值就是当前未处理元素的最大值；A 耗尽后，B[j]就是唯一候选。把它放在位置k会保持已完成后缀的不变量。循环在 B 耗尽时结束，此时后缀已经就位，A 的剩余前缀无需移动，所以整个 A 有序且包含两数组全部元素。
解题步骤
- 初始化
i = m - 1、j = n - 1、k = m + n - 1。- 只要
j >= 0，B 中仍有元素必须写入 A。- 若
i >= 0且A[i] > B[j]，把A[i]放到A[k]；否则放入B[j]。相等时取哪一侧都正确，这里统一取 B。- 每写入一个元素，就把对应读指针和
k左移一位；B 耗尽后结束。以
A = [1,2,3,0,0,0]、B = [2,5,6]为例，写入顺序依次是6、5、3、2，此时 B 耗尽，A 的[1,2]已在原位，结果为[1,2,2,3,5,6]。m = 0时循环会完整复制 B；n = 0时循环不执行，A 保持不变。
代码实现
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && A[i] > B[j]) {
A[k--] = A[i--];
} else {
A[k--] = B[j--];
}
}
}
}
func merge(A []int, m int, B []int, n int) {
i, j, k := m-1, n-1, m+n-1
for j >= 0 {
if i >= 0 && A[i] > B[j] {
A[k] = A[i]
i--
} else {
A[k] = B[j]
j--
}
k--
}
}
复杂度分析
- 时间复杂度：
O(m + n)。每轮确定一个最终位置，最坏情况下处理两个数组的全部元素。- 空间复杂度：
O(1)。只使用三个下标，直接复用 A 末尾的预留空间。
关键点总结
- 空位在 A 的尾部，决定了应从后往前写；方向选择直接消除了读写覆盖。
A[k+1..]始终是已经确定的有序后缀，这是合并正确性的核心不变量。- 循环条件只盯住 B：B 的剩余元素必须搬运，A 的剩余元素天然已在正确位置。
k = m + n - 1、i = m - 1，必须区分总容量与有效长度。
易错点总结
- 从前往后直接覆盖 A：
A = [1,2,3,0,0,0]、B = [0,0,0]时，首轮就会覆盖尚未读取的 1，后续无法恢复。- 把
i初始化为A.length - 1：预留位置的 0 会被当作有效元素参与比较。i必须从m - 1开始。- 把
k初始化为m + n：第一次写入即越界；最后一个合法位置是m + n - 1。- 主循环只写
i >= 0 && j >= 0，却漏掉 B 的收尾：A = [0], m = 0, B = [1], n = 1时循环不执行，结果仍为[0]。用本文的j >= 0单循环可自然覆盖这一边界。- 循环条件使用
i >= 0 || j >= 0后仍直接访问两侧：任一指针变成 -1 都会越界；应先判断指针有效性，或采用本文的分支结构。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 88. 合并两个有序数组 | 简单 | 完全同构的题面，可直接对照检验指针初值与收尾循环是否写对 |
| 21. 合并两个有序链表 | 简单 | 载体换成链表后无法逆向遍历，必须正向合并并借助哑结点串接 |
| 23. 合并 K 个升序链表 | 困难 | 待合并序列从 2 条扩展到 K 条，需要优先队列或分治来降低每步选择的代价 |
| 977. 有序数组的平方 | 简单 | 双指针从两端向中间收缩而非从末端同向左移，考察对最大值来源的判断 |
| 986. 区间列表的交集 | 中等 | 双指针推进的元素是区间而非单值，每步要计算重叠而不是简单取较大者 |
| 283. 移动零 | 简单 | 同样是原地写指针追读指针，但方向为正向，靠「写指针永不超前」保证安全 |