合并两个有序数组
Merge Sorted Array
本机进度仅保存在当前浏览器
题目描述
nums1 与 nums2 均为非递减排列，nums1 的末尾预留了恰好容纳 nums2 的空间（用 0 占位）。请把 nums2 合并进 nums1，使合并后的数组仍然有序，要求原地完成。
示例：nums1 = [1, 2, 3, 0, 0, 0]，nums2 = [2, 5, 6]，合并后 nums1 = [1, 2, 2, 3, 5, 6]。
解题思路
- 正向合并会把 nums1 未处理的元素覆盖掉，而nums1 的尾部是空位——所以从后往前填。
- 用三个指针分别指向 nums1 有效部分的末尾、nums2 的末尾、以及整个数组的写入末尾。
- 每一步把两指针所指中较大的数放进写入位，哪个用完就把剩余部分整体搬入。
- nums2 先耗尽时 nums1 前缀本来就在正确位置，无需额外处理。
参考实现
查看参考实现Python · 建议先自行作答
def merge(nums1, m, nums2, n):
# 从后往前填充，避免覆盖 nums1 未处理元素
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1