两个数组原地合并详解：双指针从后向前才是最优解
🚀 两个数组原地合并详解：双指针从后向前才是最优解
两个有序数组原地合并时，最优方案并不是从前往后插入，而是利用 nums1 预留空间，从数组尾部开始比较，采用三个指针从后向前填充数据，时间复杂度 O(m+n)，空间复杂度 O(1)。
1️⃣ 问题背景
这是面试中出现频率极高的一道经典题目，也是很多公司考察双指针思想的入门题。
题目通常描述如下：
m = 3
nums2 = [2,5,6]
n = 3
要求将 nums2 合并到 nums1 中，并且结果仍然保持有序。
最终结果：
题目特别强调：
- 不能创建新的数组
- 必须原地完成
- 要求尽可能低的时间复杂度
2️⃣ 核心原理
题目的关键条件：
例如：
其中：
- 前 m 个元素是真实数据
- 后 n 个位置是预留空间
因此：
既然尾部已经预留了空间，那么完全可以从后向前填充数据。
这样不会覆盖还未处理的数据。
3️⃣ 数据结构分析
整个过程只需要三个指针。
指针 i
指向 nums1 有效区域最后一个元素。
指针 j
指向 nums2 最后一个元素。
指针 k
指向最终数组最后一个位置。
例如：
[1,2,3,0,0,0]
↑
i=2
nums2:
[2,5,6]
↑
j=2
k=5
4️⃣ 算法分析
每次比较：
nums2[j]
较大的元素放到：
然后对应指针左移。
例如：
↓
6 放到末尾
结果：
继续：
↓
5 放到倒数第二位
结果：
直到某个数组遍历结束。
5️⃣ 执行流程
↓
比较 nums1[i] 和 nums2[j]
↓
较大元素放入 nums1[k]
↓
对应指针左移
↓
k 左移
↓
继续循环
↓
nums2 是否还有剩余元素？
↓
复制剩余元素
↓
结束
完整代码
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 (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
}
6️⃣ 实际案例
案例一
nums2 = [2,5,6]
执行过程：
↓
3 VS 5 → 放5
↓
3 VS 2 → 放3
↓
2 VS 2 → 放2
↓
2 VS 空 → 复制剩余2
最终：
案例二
m = 0
nums2 = [1]
n = 1
结果：
7️⃣ 优缺点分析
| 方案 | 时间复杂度 | 空间复杂度 | 评价 |
|---|---|---|---|
| 新数组合并 | O(m+n) | O(m+n) | 非原地 |
| 前向插入 | O(m×n) | O(1) | 效率较低 |
| 后向双指针 | O(m+n) | O(1) | 最优方案 |
8️⃣ 面试常见问题
为什么从后向前遍历？
因为 nums1 尾部存在空闲空间，从后向前填充不会覆盖未处理的数据。
为什么不用处理 nums1 剩余元素？
因为 nums1 剩余部分本身就在正确位置，无需再次复制。
为什么不会数组越界？
循环条件严格限制：
因此访问数组时下标始终合法。
k 为什么等于 m+n-1？
因为题目保证：
最后一个下标自然就是：
时间复杂度是多少？
每个元素最多访问一次：
仅使用三个变量：
9️⃣ 总结
✅ 原地合并两个有序数组的核心是利用 nums1 尾部预留空间。
✅ 使用三个指针 i、j、k 从后向前比较和填充。
✅ 避免前向插入导致的大量元素移动。
✅ 时间复杂度 O(m+n)，空间复杂度 O(1)。
✅ 这是双指针思想在数组操作中的经典应用，也是面试高频考点。
利用 nums1 预留空间，从数组尾部开始使用三个指针进行归并排序思想的合并，每次将较大元素放入末尾位置，从而实现 O(m+n) 时间复杂度和 O(1) 空间复杂度的原地合并。
上一篇：算法：递归和动态规划
下一篇： 无
相关文章
-
算法常用的函数
1、求一个数的n的m次方
NEW个对象 2025-01-13
-
两个数组原地合并详解：双指针从后向前才是最优解
两个有序数组原地合并时，最优方案并不是从前往后插入，而是利用 nums1 预留空间，从数组尾部开始比较，采用三个指针从后向前填充数据，时间复杂度 O(m+n)，空间复杂度 O(1)。
NEW个对象 2026-06-09
-
算法：递归和动态规划
用到递归的时候，方法的作用很重要。 用到动态规划的时候，dp代表的含义很重要。
NEW个对象 2025-03-07
