LeetCode 88简单双指针
合并两个有序数组 图解题解
这道题到底在问什么
nums1 长度为 m+n，前 m 个是有效值、后 n 个是 0 占位；nums2 有 n 个值。把 nums2 合并进 nums1，使 nums1 整体升序。
- 输入
- nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3
- 输出
- [1,2,2,3,5,6]
最优解：一步一步想明白
- 3记住这句「比 nums1 和 nums2 末尾、大的放到 nums1 最后空位」，下面每一帧都在套它。
- 4比较 nums1[5]=11 与 nums2[4]=10 → nums1 末尾更大。准备把较大的放进 nums1 的空位下标 10（指针 k）。
- 5把 11 放进 nums1[10]（来自 nums1，i 前移），k 前移到下一个空位。
- 6比较 nums1[4]=9 与 nums2[4]=10 → nums2 末尾更大（或相等取它）。准备把较大的放进 nums1 的空位下标 9（指针 k）。
- 7把 10 放进 nums1[9]（来自 nums2，j 前移），k 前移到下一个空位。
- 8比较 nums1[4]=9 与 nums2[3]=8 → nums1 末尾更大。准备把较大的放进 nums1 的空位下标 8（指针 k）。
- 9把 9 放进 nums1[8]（来自 nums1，i 前移），k 前移到下一个空位。
- 10比较 nums1[3]=7 与 nums2[3]=8 → nums2 末尾更大（或相等取它）。准备把较大的放进 nums1 的空位下标 7（指针 k）。
- 11把 8 放进 nums1[7]（来自 nums2，j 前移），k 前移到下一个空位。
- 12比较 nums1[3]=7 与 nums2[2]=6 → nums1 末尾更大。准备把较大的放进 nums1 的空位下标 6（指针 k）。
- 13把 7 放进 nums1[6]（来自 nums1，i 前移），k 前移到下一个空位。
- 14比较 nums1[2]=5 与 nums2[2]=6 → nums2 末尾更大（或相等取它）。准备把较大的放进 nums1 的空位下标 5（指针 k）。
- 15把 6 放进 nums1[5]（来自 nums2，j 前移），k 前移到下一个空位。
- 16比较 nums1[2]=5 与 nums2[1]=4 → nums1 末尾更大。准备把较大的放进 nums1 的空位下标 4（指针 k）。
- 17把 5 放进 nums1[4]（来自 nums1，i 前移），k 前移到下一个空位。
- 18比较 nums1[1]=3 与 nums2[1]=4 → nums2 末尾更大（或相等取它）。准备把较大的放进 nums1 的空位下标 3（指针 k）。
- 19把 4 放进 nums1[3]（来自 nums2，j 前移），k 前移到下一个空位。
- 20比较 nums1[1]=3 与 nums2[0]=2 → nums1 末尾更大。准备把较大的放进 nums1 的空位下标 2（指针 k）。
- 21把 3 放进 nums1[2]（来自 nums1，i 前移），k 前移到下一个空位。
- 22比较 nums1[0]=1 与 nums2[0]=2 → nums2 末尾更大（或相等取它）。准备把较大的放进 nums1 的空位下标 1（指针 k）。
- 23把 2 放进 nums1[1]（来自 nums2，j 前移），k 前移到下一个空位。
- 24从后往前填了 10 次，nums1 现在整体升序：[1,2,3,4,5,6,7,8,9,10,11]。三个指针各只走一遍，O(m+n)。
⚠️ 容易写错的地方
✗ 错：从前往后填
✓ 对：从后往前填
从前填会覆盖 nums1 前面还没处理的有效数字
✗ 错：循环条件写 i>=0
✓ 对：写 j>=0
nums2 并完就结束；nums1 剩下的本就在位，不用再搬
✗ 错：i 越界还去取 nums1[i]
✓ 对：先判 i>=0
nums1 取完后应直接放 nums2，否则数组越界
完整代码（Python / C++ / Java）
Python
def merge(nums1, m, nums2, n):
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0: # nums2 还没并完
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]; i -= 1 # nums1 末尾更大
else:
nums1[k] = nums2[j]; j -= 1 # 放 nums2
k -= 1C++
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n){
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j])
nums1[k--] = nums1[i--]; // nums1 末尾更大
else
nums1[k--] = nums2[j--]; // 放 nums2
}
}Java
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--]; // nums1 末尾更大
} else {
nums1[k--] = nums2[j--]; // 放 nums2 末尾
}
}
}复杂度
时间
O(m+n)
每个元素只被放一次
空间
O(1)
原地在 nums1 上填，不开新数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 合并两个有序数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 while 只判 j>=0，不判 i>=0？+
当 j<0（nums2 全部并入）时，nums1 剩下的前缀本来就在正确位置上，不需要再搬动；而只要 nums2 还有元素没并入，就必须继续。
如果不能原地、允许开新数组怎么写？+
可以从前往后双指针，开一个 m+n 的新数组依次取较小者，最后拷回 nums1。思路更直白，但空间 O(m+n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 合并两个有序数组 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。