欢迎阅读 欢迎来到「复写零」题解之旅本文将带你从“将每个零复制一份其余元素右移”这一数组操作问题出发深入理解双指针 逆向覆盖的巧妙应用并掌握如何原地修改数组避免从前往后覆盖丢失数据。在开始之前建议你先了解题目背景这是 LeetCode 1089 题给定一个固定长度的整数数组arr要求将每个0复写一次即[1,0,2]变为[1,0,0,2]但数组长度不变超出的元素被丢弃。必须原地修改不返回新数组。本质上我们需要在有限空间内模拟“插入”零并右移元素但正向操作会覆盖后续数据因此必须先确定边界再从后往前填充。明确学习目标掌握双指针逆向法——第一步用left遍历数组right模拟“复写后”的位置找到最后一个会被复写到的位置即right到达末尾或超过末尾从而确定实际复写范围同时处理特殊情况若最后一个复写导致right n说明最后一个元素是零且只能复写一次需单独处理。第二步从left开始从后往前覆盖遇到零则写入两个零否则写入原数确保不丢失数据。理解这种“先定位边界再逆向回填”的策略为什么能避免覆盖问题并熟练实现边界条件和循环逻辑。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如arr [1,0,2,3,0,4,5,0]输出[1,0,0,2,3,0,0,4]。本文将从问题转化、双指针定位边界、逆向覆盖实现到代码模拟层层递进。即使你对双指针还不熟悉我们也会从“先算好每个零要占两个位置再倒着填回去”这一直觉出发让你轻松抓住核心思想——从前往后看从后往前写就能做到原地且不丢失。现在让我们一起把零复写一遍让数组在有限长度内焕发新生吧 一.题目1089. 复写零 - 力扣LeetCode 欢迎来到「复写零」题解之旅本文将带你从“在数组中复制零并右移元素”这一模拟操作出发深入理解双指针 逆向填充的巧妙应用并掌握如何原地修改数组避免覆盖未处理数据。在开始之前建议你先了解题目背景这是 LeetCode 1089 题给定一个固定长度数组arr要求将每个0复写一次即[1,0,2]变为[1,0,0,2]但数组长度不变超出部分会被丢弃必须原地修改。本质上是模拟“插入”零但正向操作会覆盖后续数据因此必须反向操作。明确学习目标掌握双指针逆向法——先通过一次遍历确定最后一个会被保留的元素位置模拟复写后的总长度同时处理边界情况如最后一个复写溢出。然后从后往前填充数组遇到零则写两个零否则写原数保证不丢失任何数据。理解为什么这种“从后向前先定位再填充”的策略是最优的并熟练实现边界判断。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如arr [1,0,2,3,0,4,5,0]输出[1,0,0,2,3,0,0,4]。本文将从问题转化、双指针定位边界、逆向回填实现到代码模拟层层递进。即使你对双指针还不熟悉我们也会从“先数清楚需要占几个位置再从末尾倒着填”这一直觉出发让你轻松抓住核心思想——正向确定范围逆向执行写入原地操作不丢数据。现在让我们一起把零复写一遍让数组在长度不变的情况下完成“扩容”吧 二.做题思路一、问题分析前置分析给定一个整数数组arr要求将每个出现的0 复写一遍其余元素向右平移不能超出数组长度。必须原地修改不返回任何内容。核心思路先模拟复写过程确定哪些元素会被保留然后从右向左进行填充避免覆盖尚未处理的数据。二、算法策略双指针 逆向填充阶段一定位边界使用双指针left和rightleft遍历原数组right模拟复写后的位置偏移。若arr[left] ! 0则right 1只占一个位置若arr[left] 0则right 2复写后占两个位置。当right n - 1时说明已确定最后一个需要处理的位置停止移动。阶段二处理边界若right n说明最后一个位置是 0 且该 0 只能复写一次则将数组末尾置 0并回退指针。阶段三逆向填充从left开始从右向左遍历若arr[left] 0则在right和right-1位置各写一个 0right - 2否则将arr[left]写入right位置right - 1每次循环left--直到处理完所有元素。示例执行过程以arr [1, 0, 2, 3, 0, 4, 5, 0]为例n 8步骤leftarr[left]操作right模拟right值说明初始01right 10非零只占1位110right 22零复写占2位222right 13非零333right 14非零440right 26零复写554right 17非零此时right 7 n-1停止结束left5--right7确定最后一个元素为原arr[5]4此时left5right7表示原数组前 6 个元素下标 0~5会被保留到新数组复写后的有效位置为 0~7。接着逆向填充从后往前写防止覆盖步骤leftarr[left]操作right变化数组状态关键位置初始54非零写一次right7→ 6arr[7]4140零写两次right6→ 4arr[6]0, arr[5]0233非零写一次right4→ 3arr[4]3322非零写一次right3→ 2arr[3]2410零写两次right2→ 0arr[2]0, arr[1]0501非零写一次right0→ -1arr[0]1三、正确性说明简单版本结合示例上述示例展示了算法的正确性先定位保证了最后一个被保留的元素及其对应位置被正确找出从右向左填充避免了覆盖尚未处理的原始数据因为右侧位置已经被“预留”左侧元素尚未被修改。整个过程中每个需要保留的元素都被准确移到最终位置0 被复制两次但不会超出边界最终得到正确结果。该算法一次定位加一次填充时间复杂度 O(n)且原地完成。四、实现细节边界防护使用left和right两个指针right初始为-1。阶段一循环中当right n-1时立即breakleft不再自增。阶段二检测right n情况例如arr [0]时right会变成 2但 n1right2 0breakleft0阶段二right n成立执行特殊处理。特殊处理arr[n-1] 0; left--; right - 2;回退到有效位置。逆向填充时注意right不能为负但循环条件left 0且right会同步回退不会越界。时间复杂度 O(n)空间复杂度 O(1)。五、返回值目标映射不需要返回值函数直接修改原数组arr使每个 0 被复写一次其余元素向右平移。三.代码#include iostream #include vector using namespace std; class Solution { public: void duplicateZeros(vectorint arr) { // 算法思路先确定原数组中哪些元素会被保留或复制到新数组中 // 然后从右向左覆盖原数组避免从左向右覆盖时丢失数据。 // 使用双指针left 遍历原数组right 表示在“复制零”后的新数组中的位置索引。 int left 0; // 原数组遍历指针 int right -1; // 新数组逻辑上的索引初始为-1 int n arr.size(); // 阶段一查找最后一个需要处理的元素确定 left 和 right 的终止位置 // 模拟“复制零”的过程但不实际修改数组只计算每个元素在新数组中的结束位置。 while (left n) { // 如果当前元素不是0复制后占据1个位置 if (arr[left] ! 0) { right 1; } else { // 如果当前元素是0复制后占据2个位置因为要复制一个0 right 2; } // 如果 right 已经达到或超过最后一个有效索引n-1停止查找 // 因为后面的元素即使存在也会被舍弃新数组长度固定为 n。 if (right n - 1) { break; } // 只有 right 没有越界时left 才能继续前进因为后续还有空间容纳更多元素 left; } // 阶段二处理特殊情况right 恰好等于 n超出边界一个位置 // 这种情况发生最后一个元素是0且复制后原本应占据两个位置但只容得下一个 // 因此新数组的最后一个位置arr[n-1]被置为0且该0只能复制一次。 if (right n) { arr[n - 1] 0; // 最后一位放0 left--; // left 回退到上一个元素原数组中的最后一个有效元素 right - 2; // right 回退到上一个元素应占的最后位置跳过最后一位 } // 阶段三从右往左填充原数组利用 left 和 right 指针 // left 指向原数组中最后一个需要处理的元素right 指向新数组中对应的最后位置。 // 从后往前写避免覆盖尚未处理的数据。 while (left 0) { if (arr[left] 0) { // 如果当前元素是0需要复制两次在 right 和 right-1 位置都写0 arr[right] arr[left]; arr[right - 1] arr[left]; right - 2; // 右指针回退两个位置 } else { // 如果当前元素不是0只需写一次 arr[right] arr[left]; right - 1; // 右指针回退一个位置 } left--; // 左指针回退继续处理前一个元素 } } }; int main() { // 新的调试案例一个包含零的数组用于观察复制零的过程 vectorint arr {0, 1, 0, 2}; Solution sol; sol.duplicateZeros(arr); for (int x : arr) { cout x ; } cout endl; return 0; }四、易错点分析4.1 阶段一循环中left的递增条件只有right未越界时才递增if (right n - 1) { break; } left;易错原因在模拟复制零的过程中right可能提前达到或超过n-1此时应立即跳出循环不应再执行left。若误将left写在if外面无条件递增会导致left多前进一位使得后续阶段二和阶段三中left指向错误的元素最终漏处理或重复处理某个元素。正确逻辑是只有right n-1时即还有空间容纳后续元素left才前进否则终止查找。4.2 特殊情况right n时的指针回退细节if (right n) { arr[n - 1] 0; left--; right - 2; }易错原因当right n时表示最后一个元素是0且复制后超出边界一位新数组最后一位必须置为0只复制一次。此时需要回退指针以便从正确位置开始从右向左填充。left--回退到原数组最后一个有效元素right - 2跳过已处理的最后一位。若只写right--或left不回退会导致填充时位置错乱比如right指向n-1却误以为最后一位已填好重复覆盖或遗漏。必须严格按此回退量调整。4.3 阶段三填充时对0的复制两次操作与指针递减步长if (arr[left] 0) { arr[right] arr[left]; arr[right - 1] arr[left]; right - 2; } else { arr[right] arr[left]; right - 1; } left--;易错原因从右向左填充时若当前元素是0需在right和right-1两个位置写0然后right必须减2跳过两个已填位置若非零则只填一个位置right减1。初学者容易在0分支写成right - 1导致后续覆盖重叠或留下空洞。同时left--每轮必执行但若0分支中right-1可能越界由于阶段一和阶段二已确保right始终 ≥ 1除非数组长度为0但题目长度≥1因此安全。务必保证right的递减步长与复制次数一致。五、流程图 闭幕 恭喜你完成了「复写零」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题要求原地修改数组将每个零复写一次其他元素右移。代码使用了双指针left和right先确定哪些元素需要被保留再从后向前写回。请问left和right在第一次遍历查找最后一个需要处理的元素中分别代表什么含义为什么right初始为-1而不是0第一次遍历时当遇到非零right 1遇到零right 2。为什么零要加2这背后的逻辑核心是什么在第一次遍历结束后有一个if (right n)的特殊分支将数组最后一个元素赋零并调整指针。这个分支处理的是边界越界情况请举例说明它何时触发。第二次遍历是从left到0从右向左写回为什么要从右向左写如果从左向右写会覆盖未处理数据你能具体说明吗本题要求不要返回任何东西就地修改但 LeetCode 的测试用例会检查arr是否被正确修改。如果在函数内部新建一个临时数组去复制再赋值回arr虽然也能通过但违反了“就地”的核心要求这种做法在面试中会被如何看待延伸挑战如果要求复写所有值为某特定数字不一定是零的元素代码应如何通用化改造请给出关键修改思路。思考本题与移动零的异同两者都涉及零的处理但复写零要求保留零且复制而移动零是将零移到末尾它们的双指针方向有何不同为什么一个需要从右向左另一个从左向右如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案left是原数组扫描指针慢指针用于遍历arr并判断每个元素是否是零right是扩展后的索引快指针模拟复写零后总长度的位置初始为-1是因为还没有处理任何元素每次移动后right指向当前已处理元素在“假想新数组”中的最后一个位置。遇到非零新数组长度增加1right 1遇到零零被复写一次所以新数组增加两个位置right 2这正是为了模拟复写零的效果。right n的情况表示最后一个元素是零且复写后刚好越界一个位置例如arr [0,0]此时最后一个位置应补零right回退2left减1即只复制一次零避免越界写入。必须从右向左写因为若从左向右写未处理的元素会被覆盖丢失从右向左能保证只覆盖已处理区域不影响左侧还未读取的元素。新建临时数组再复制回arr虽然结果正确但额外使用了O(n) 空间违背了“就地”的要求面试中会被视为不符合题意因此应坚持双指针原地修改。延伸挑战答案挑战1将判断条件从arr[left] 0改为arr[left] target目标值同时复写时将target写入两次其余逻辑双指针、边界处理完全不变即实现了通用化复写任意指定值。挑战2复写零需要从右向左操作因为复写会增加元素从左向右会覆盖后方未处理数据造成信息丢失而移动零是将零向后推减少零的位置从左向右用快慢指针不会覆盖未处理元素因此方向相反本质区别在于操作是否会改变数组长度。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
