必须从后往前合并,因为从前向后会覆盖nums1未处理的有效元素;利用尾部空余空间,用三指针i=m-1、j=n-1、k=m+n-1比较填入最大值,确保不丢失数据且原地完成。

为什么不能直接从前往后合并
从头开始合并两个有序数组(比如把 nums2 合并进 nums1)会覆盖 nums1 中还没处理的元素。因为 nums1 末尾预留了空间,但前面是有效数据,一旦用 nums1[i] = nums2[j] 覆盖了某个位置,原来那个值就丢了——后续没法参与比较。
必须从后往前合并的逻辑
利用 nums1 的「空余尾部」作为临时落脚点:把当前最大的元素放到 nums1 最后一个可用位置,逐步向前填。这样既不破坏未处理数据,又能复用原空间。
-
nums1的有效长度是m,总长度是m + n,所以最后一个写入位置初始为m + n - 1 - 维护三个指针:
i = m - 1(nums1有效尾)、j = n - 1(nums2尾)、k = m + n - 1(合并目标位置) - 每次比较
nums1[i]和nums2[j],大的那个赋给nums1[k],对应指针前移 - 当
i 时,把剩余 <code>nums2全部拷过去;当j 时,<code>nums1剩余部分已在位,无需操作
边界处理最容易漏的两种情况
很多人只考虑双方都还有元素可比,却忽略一方提前耗尽的情况。尤其当 nums2 还剩元素而 nums1 已遍历完时,必须手动拷贝,否则结果缺失。
while (j >= 0) {
nums1[k--] = nums2[j--];
}
而 i >= 0 时不用管——因为那些元素本来就在 nums1 的正确前段位置上。另外注意:如果 m == 0,整个 nums1 是空容器,要靠上面这个循环把 nums2 完整搬进来。
原地合并的代价和适用前提
这个解法要求 nums1 预留了足够空间(即 nums1.size() == m + n),否则越界。它时间复杂度是 O(m + n),空间复杂度是 O(1),但实际修改的是 nums1 本身——如果你还需要原始 nums1,就得先备份。
真正的难点不在循环逻辑,而在想清楚“谁该先停、谁该补、补到哪”——尤其是 j 指针扫完后是否还有残留,这点在测试用例 m=0 或 n=0 时立刻暴露。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











