AlgoViz Lab交互式算法学习Algorithms first
合并两个有序数组 · 交互式算法学习
把 nums2 合并进 nums1，并保持升序。
#88 · 数组 / 字符串
合并两个有序数组
Merge Sorted Array
nums1 = [1,2,3,0,0,0], nums2 = [2,5,6]线性序列9 个关键状态
步骤 1读指针指向两个数组末尾，写指针位于最右空位。
i=2, j=2, write=51
02
1i
3
20
30
4write
0
5推荐
从后向前双指针
时间
O(m+n)空间 O(1)从最大值开始写入 nums1 的尾部，不会覆盖仍待比较的数据。
1function merge(nums1, m, nums2, n) {2 let i = m - 1,3 j = n - 1,4 write = m + n - 1;5 while (j >= 0) {6 if (i >= 0 && nums1[i] > nums2[j]) {7 nums1[write--] = nums1[i--];8 } else {9 nums1[write--] = nums2[j--];10 }11 }12}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public void merge(int[] nums1, int m, int[] nums2, int n) {3 for (int i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) {4 nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];5 }6 }7}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
合并两个有序数组 · 解法对比
把 nums2 合并进 nums1，并保持升序。
- 测试用例
nums1 = [1,2,3,0,0,0], nums2 = [2,5,6]- 题目分类
- 数组 / 字符串
- 解法对比
- 2
合并后排序
先利用尾部空位装入 nums2，再整体排序。简单，但没有利用两个数组已经有序。
- 时间
O((m+n) log(m+n))- 空间
O(1)
从后向前双指针
从最大值开始写入 nums1 的尾部，不会覆盖仍待比较的数据。
- 时间
O(m+n)- 空间
O(1)
为什么有效
nums1 的尾部预留了空位。从右向左写入时，尚未处理的有效元素都在写指针左侧，因此不会覆盖仍需比较的数据。
关键不变量
每一步结束后，write 右侧已经是最终答案中最大的若干元素，且保持有序。
易错点
- 不要从左向右原地写入，否则会覆盖 nums1 中尚未比较的元素。
- 循环条件只需保证 nums2 尚未用完；nums1 剩余前缀本来就在正确位置。
边界情况
- nums2 为空时 nums1 不变。
- nums1 的有效部分为空时，应完整复制 nums2。
- 两个数组包含相同值时仍要正确移动写指针。
更多案例
nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3[1,2,2,3,5,6]从右向左依次写入 6、5、3、2。
nums1=[1], m=1, nums2=[], n=0[1]nums2 为空，不进入循环。
nums1=[0], m=0, nums2=[1], n=1[1]nums1 没有有效元素，直接写入 nums2。