题目链接

LeetCode复写零

题目描述

 

题目解析

一、问题理解

题目要求：给定一个整数数组 arr，在不创建新数组的情况下，将每个出现的 0 复写一遍（即一个 0 变成两个 0），同时保持其他元素的相对顺序不变。复写后超出原数组长度的元素需要舍弃。

示例：

• 输入：[1,0,2,3,0,4,5,0]
• 输出：[1,0,0,2,3,0,0,4]

 核心难点：

1. 必须在原数组上操作（空间复杂度 O(1)）
2. 复写 0 会改变后续元素的位置，直接从左到右处理会覆盖未处理的元素

 

二、解题思路：双指针法

为解决上述问题，我们采用「双指针 + 两次遍历」的策略：

第一次遍历：确定最终需要保留的元素范围（找到复写边界）  

第二次遍历：从边界处从右向左复写元素（避免覆盖未处理的元素） 

 

三、分步解析代码

以下是完整代码，我们逐部分解析： 

 

四、关键步骤详解

1. 寻找复写边界（第一次遍历）

• 目的：确定原数组中哪些元素需要参与复写（避免处理超出最终数组长度的元素）。
• 双指针作用：
  • cur：遍历原数组的每个元素（从左到右）。
  • dest：模拟复写后的数组长度（每遇到 0 加 2，非 0 加 1）。
• 终止条件：当 dest >= n-1 时停止（复写指针已超出数组范围）。

示例过程（输入 [1,0,2,3]，n=4）：

• 初始：cur=0，dest=-1
• cur=0（元素 1）：dest +=1 → 0，dest < 3，cur→1
• cur=1（元素 0）：dest +=2 → 2，dest < 3，cur→2
• cur=2（元素 2）：dest +=1 → 3，dest == 3（n-1），停止遍历。
• 最终：cur=2，dest=3（复写边界确定）。

2. 处理边界情况

• 特殊场景：当 dest == n 时，说明最后一个元素是 0，且复写后会超出数组长度（例如输入 [0,1,2]，复写后 dest 会达到 3，等于 n=3）。
• 处理方式：
  • 最后一个 0 只能复写 1 次（放在数组末尾 arr[n-1]）。
  • 调整指针：cur 回退 1（跳过该 0 的二次处理），dest 回退 2（指向 n-2）。

3. 从右向左复写（第二次遍历）

• 核心逻辑：从 cur 位置向左遍历，将元素复写到 dest 位置（避免覆盖未处理的元素）。
• 复写规则：
  • 非 0 元素：直接复制到 dest 位置，然后双指针左移。
  • 0 元素：连续复制两个 0 到 dest 和 dest-1 位置，然后双指针左移。

示例过程（续上例 [1,0,2,3]）：

• 初始：cur=2，dest=3
• cur=2（元素 2）：arr[3] = 2，dest→2，cur→1
• cur=1（元素 0）：arr[2] = 0，arr[1] = 0，dest→0，cur→0
• cur=0（元素 1）：arr[0] = 1，dest→-1，cur→-1
• 最终结果：[1,0,0,2]（符合预期）。

五、复杂度分析

• 时间复杂度：O(n)，两次遍历数组，总操作次数与数组长度成正比。
• 空间复杂度：O(1)，仅使用常数个额外变量，在原数组上操作。

通过这种双指针策略，我们高效地解决了复写零的问题，既保证了原地操作，又避免了元素覆盖的问题。关键在于先确定复写边界，再从后往前处理，这是解决类似「原地修改数组」问题的常用技巧。