LeetCode 88. 合并两个有序数组
题目描述
题意分析
两个数组都已按非递减顺序排列，也就是从小到大排列，允许出现重复值。需要把它们的所有有效元素合并，结果仍然有序，重复元素也要保留。
合并结果直接存入
nums1，不需要返回新数组。nums1的长度是m + n，但只有前m个元素参与合并，后n个位置只是预留空间；nums2的n个元素全部参与合并。有效范围由m和n决定，不能靠元素是否为0判断。
解法：从后往前双指针
核心思路
[!blue]
两个数组已经有序，各自未合并部分的最后一个元素就是这一部分的最大值。比较这两个值，把较大的放到结果的最后一个空位，再继续向前填，就能得到有序结果，无需重新排序。
从后往前写，是为了保护
nums1中还没参与比较的元素：从前往后写时，放入nums2的元素可能覆盖它们；而尾部有预留空间，只要nums2还有元素没放入，写入位置就始终在nums1未合并部分的右侧，不会覆盖未读数据。这个空位关系会一直保持：待填位置需要容纳两个数组中全部剩余元素，而
nums1的未读部分只占其中一部分。只要nums2还有剩余，待填区间就比nums1的未读区间更长，所以最右侧的写入位置不会落进未读部分。每次写入一个元素后，待填数量与剩余元素数量一起减少，关系仍然成立。如果
nums1的有效元素先用完，就继续把nums2的剩余元素向前填入。如果nums2先用完，nums1剩下的元素本来就在前面，顺序和位置都正确，无需移动。因此，循环只需要判断nums2是否还有元素。
解题步骤
- 令
i = m - 1、j = n - 1，分别指向两个数组的有效末尾；k = m + n - 1指向写入位置。- 当
j >= 0时，若i >= 0且nums1[i] > nums2[j]，把nums1[i]写入nums1[k]，并将i左移；否则写入nums2[j]，并将j左移。- 将写指针
k左移，重复上一步。j < 0时结束；nums1的剩余元素无需移动。
代码实现
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
// 倒序写入位置始终在未读的第一数组右侧；第二数组写完后，剩余前缀已就位。
while (j >= 0) {
// 第一数组可能先耗尽，先判断读下标再比较。
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
}
func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
// 倒序写入位置始终在未读的第一数组右侧；第二数组写完后，剩余前缀已就位。
for j >= 0 {
// 第一数组可能先耗尽，先判断读下标再比较。
if i >= 0 && nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
}
复杂度分析
- 时间复杂度：$O(m + n)$，每次写入一个元素，最多写入
m + n次。- 空间复杂度：$O(1)$，只使用三个下标变量，直接在
nums1中完成合并。
关键点总结
[!green]
- 从后往前放较大值，避免覆盖
nums1中尚未读取的元素。- 判断条件先检查
i >= 0，再访问nums1[i]。- 循环只需保证
nums2耗尽，nums1的剩余部分天然有序且位置正确。
易错点总结
[!yellow]
- 从前往后原地合并，会覆盖
nums1的未读元素。- 把
i初始化为nums1.length - 1，会把尾部占位符当成有效数据；应使用m - 1。- 主循环只比较两边都有元素的情况，却忘记继续写入
nums2的剩余元素。i < 0后仍访问nums1[i]，会导致数组越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 21. 合并两个有序链表 | 简单 | 同样合并两个有序序列，本题数组前段可能被写入覆盖，因此常从大到小往后填。 |
| 977. 有序数组的平方 | 简单 | 同样从两端获取较大候选并从输出末尾写入，避免额外排序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！