合并两个有序数组的高效算法详解

---

合并两个有序数组的高效算法详解

1. 问题描述

给定两个按 非递减顺序 排列的整数数组 nums1 和 nums2，以及两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。

要求：

• 将 nums2 合并到 nums1 中，使合并后的数组仍然保持 非递减顺序。
• nums1 的初始长度为 m + n，其中后 n 个元素为 0，表示应被 nums2 填充的位置。

示例：

输入：
nums1 = [1, 2, 3, 0, 0, 0], m = 3  
nums2 = [2, 5, 6], n = 3输出：
[1, 2, 2, 3, 5, 6]

---

2. 常见解法分析

方法 1：合并后排序（暴力法）

思路：

1. 将 nums2 的所有元素直接放入 nums1 的末尾。
2. 对整个 nums1 进行排序。

代码：

public void merge(int[] nums1, int m, int[] nums2, int n) {for (int i = 0; i < n; i++) {nums1[m + i] = nums2[i];}Arrays.sort(nums1);
}

复杂度分析：

• 时间复杂度：O((m+n) log(m+n))（排序的时间复杂度）
• 空间复杂度：O(1)（未使用额外空间）

缺点：

• 没有利用 nums1 和 nums2 已经有序 的特性，导致时间复杂度较高。

---

方法 2：双指针法（额外空间）

思路：

1. 创建一个临时数组 temp，用两个指针分别遍历 nums1 和 nums2，按顺序选择较小的元素放入 temp。
2. 最后将 temp 复制回 nums1。

代码：

public void merge(int[] nums1, int m, int[] nums2, int n) {int[] temp = new int[m + n];int i = 0, j = 0, k = 0;while (i < m && j < n) {if (nums1[i] <= nums2[j]) {temp[k++] = nums1[i++];} else {temp[k++] = nums2[j++];}}while (i < m) temp[k++] = nums1[i++];while (j < n) temp[k++] = nums2[j++];System.arraycopy(temp, 0, nums1, 0, m + n);
}

复杂度分析：

• 时间复杂度：O(m + n)
• 空间复杂度：O(m + n)（需要额外数组）

缺点：

• 需要额外的 O(m+n) 空间，不符合题目对空间复杂度的优化要求。

---

3. 最优解法：双指针从后向前合并

核心思路

由于 nums1 的后面有足够的空间（填充 0），我们可以 从后向前 合并，避免覆盖 nums1 前面的数据。

步骤：

1. 初始化三个指针：
   • i = m - 1（nums1 有效部分的末尾）
   • j = n - 1（nums2 的末尾）
   • k = m + n - 1（nums1 最终合并后的末尾）
2. 比较 nums1[i] 和 nums2[j]，将较大的数放入 nums1[k]，并移动指针。
3. 如果 nums2 还有剩余元素，直接复制到 nums1 前面。

代码实现

public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1, j = n - 1, k = m + n - 1;while (j >= 0) {  // 只需要处理 nums2 剩余元素if (i >= 0 && nums1[i] > nums2[j]) {nums1[k--] = nums1[i--];} else {nums1[k--] = nums2[j--];}}
}

复杂度分析

• 时间复杂度：O(m + n)（只需遍历 nums1 和 nums2 各一次）
• 空间复杂度：O(1)（原地修改，无额外空间）

示例演示

输入：

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

执行过程：

步骤	i	j	k	nums1[i]	nums2[j]	操作	nums1 结果
1	2	2	5	3	6	nums1[5] = 6	[1,2,3,0,0,6]
2	2	1	4	3	5	nums1[4] = 5	[1,2,3,0,5,6]
3	2	0	3	3	2	nums1[3] = 3	[1,2,3,3,5,6]
4	1	0	2	2	2	nums1[2] = 2	[1,2,2,3,5,6]
5	1	-1	1	-	-	j < 0 退出循环	合并完成

最终结果：

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

---

4. 关键点总结

1. 为什么从后向前合并？

   • nums1 后面有足够的空间，不会覆盖未处理的元素。
   • 如果从前向后合并，需要额外空间存储被覆盖的数据。

2. 为什么 while (j >= 0) 就够了？

   • 只要 nums2 合并完成，nums1 剩余部分已经在正确位置，无需处理。

3. 边界情况处理：

   • nums1 为空 → 直接复制 nums2。
   • nums2 为空 → nums1 保持不变。

---

5. 扩展思考

• 如果 nums1 和 nums2 不是有序的，如何优化？
  → 先排序再合并，但时间复杂度会上升至 O((m+n) log(m+n))。

• 如果要求返回新数组而不是修改 nums1？
  → 可以用 方法 2（双指针 + 额外空间）。

---

6. 总结

方法	时间复杂度	空间复杂度	适用场景
合并后排序	O((m+n) log(m+n))	O(1)	简单但效率低
双指针（额外空间）	O(m+n)	O(m+n)	需要新数组时
双指针（原地合并）	O(m+n)	O(1)	最优解

推荐使用双指针从后向前合并，既高效又节省空间！ 🚀