当前位置：首页 > news >正文

优选算法力扣1089.复写零双指针原地修改 C++解题思路每日一题

news 2025/8/3 11:44:45

零、题目描述
一、为什么这道题值得你花几分钟看懂？
二、从“异地”到“就地”：思路的自然推导
三、双指针实现：前探+回填
四、完整代码与解析
- 完整代码（附详细注释）
- 代码走读（示例1：`[1,0,2,3,0,4,5,0]`）
- 复杂度分析
五、常见问题与解决方案
六、举一反三

零、题目描述

题目链接：复写零

题目描述：
给你一个长度固定的整数数组，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意：请不要在超过该数组长度的位置写入元素。要求：对输入的数组 **就地** 进行上述修改，不要从函数返回任何东西。

示例 1：
输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]

示例 2：
输入：arr = [1,2,3]
输出：[1,2,3]

提示：
1 <= arr.length <= 10^4
0 <= arr[i] <= 9

一、为什么这道题值得你花几分钟看懂？

如果你已经搞定了「移动零」，或许会觉得这道题不过是多了个“复制”的小动作——但就是这个看似简单的“复制”，直接让问题难度上了个档次。它不光要保住元素的原有顺序，还得搞定“一个变俩”带来的长度膨胀，最后还得严丝合缝地塞进原数组的长度里，可比单纯挪元素要考验对细节的拿捏。

这道题的妙处在于，它能帮你搭起“从直觉解法到高效解法”的思维桥梁：先放开手脚想想“要是能另开一个数组该多简单”，再慢慢琢磨“怎么把额外空间省掉，在原数组上搞定一切”。这种从“宽松条件”到“严苛限制”的推导思路，在字符串替换、数组重排这类原地操作题里特别管用，算得上是算法优化的核心心法了。

要是对双指针在原地改数组的基础玩法还不太熟，不妨先看看我写的移动零这篇博客，打牢基础再啃这道题，进阶技巧理解起来会顺很多~

二、从“异地”到“就地”：思路的自然推导

1. 先想简单的：如果允许用新数组（异地操作）

拿到题的第一反应往往是：开一个新数组，遍历原数组，遇到非零元素就放一个，遇到零就放两个，直到填满新数组。比如示例1：

原数组：[1,0,2,3,0,4,5,0]
新数组构建过程：
1 → 放1 → [1]
0 → 放0、0 → [1,0,0]
2 → 放2 → [1,0,0,2]
3 → 放3 → [1,0,0,2,3]
0 → 放0、0 → [1,0,0,2,3,0,0]
4 → 放4 → [1,0,0,2,3,0,0,4]（已填满，后面的5、0忽略）

这种方法简单直接，符合直觉，但题目要求“就地修改”，不能用额外数组——所以必须想办法在原数组上实现这个逻辑。

2. 尝试就地修改：发现覆盖问题

如果直接在原数组上正向操作，会遇到一个致命问题：复写的零会覆盖还没处理的元素。比如 [1,0,2]：

遇到0时，需要在它后面再放一个0，此时会把2覆盖成0，导致2丢失。
最终结果会变成 [1,0,0]（正确），但如果数组更长，比如 [1,0,2,3]，正向复写0后会覆盖2，后续3的处理也会出错。

这说明：正向操作会破坏未处理的元素，必须换一种思路。

3. 突破口：先确定最终位置，再反向填充

既然正向会覆盖，那不如反过来——先算出每个元素最终应该在的位置，再从后往前填。这样每个元素被处理时，它原来的位置已经没用了，不用担心覆盖。

比如示例1，我们先通过“前探”确定：

原数组中的1最终在位置0，0最终在位置1和2，2在位置3，3在位置4，0在位置5和6，4在位置7。
然后从最后一个有效元素（4）开始，把它放到位置7，再处理前面的0，依次往前填。

这种“先探位置，再反向填”的思路，完美解决了覆盖问题。

三、双指针实现：前探+回填

1. 双指针的分工

需要两个指针配合：

cur：遍历原数组，探索每个元素的位置（类似异地操作时的遍历指针）。
dest：模拟复写后的位置（非零元素+1，零元素+2），用于确定最终边界。

2. 步骤拆解

第一步：前探阶段——确定有效元素范围
遍历原数组，用 dest 模拟复写后的长度，直到 dest 触达数组边界。此时 cur 前面的元素都是复写后会被保留的（后面的元素会被截断）。

int cur = 0, dest = -1;
while (cur < n) {// 0占2个位置，非0占1个dest += (arr[cur] == 0) ? 2 : 1;// 若已到达数组边界，停止探索if (dest >= n - 1) break;cur++;
}

第二步：边界修正——处理越界情况
如果最后一个元素是0，且复写后 dest 超出数组长度（比如 [0,0,0]，dest 会达到5，超过长度2），此时只能保留一个0在末尾，修正 cur 和 dest 到有效位置。

if (dest > n - 1) {arr[n - 1] = 0; // 保留一个0dest -= 2;      // 回退到有效位置cur--;          // 对应cur回退
}

第三步：回填阶段——反向填充元素
从 cur 开始反向遍历，将元素放到 dest 位置：非零元素直接放，零元素放两个。

while (cur >= 0) {if (arr[cur] != 0) {arr[dest--] = arr[cur--]; // 非零元素直接复制} else {arr[dest--] = 0;          // 零元素复写第一个0arr[dest--] = 0;          // 复写第二个0cur--;}
}

四、完整代码与解析

完整代码（附详细注释）

#include <vector>
using namespace std;class Solution {
public:void duplicateZeros(vector<int>& arr) {const int n = arr.size();if (n == 0) return; // 空数组直接返回int cur = 0, dest = -1;// 前探阶段：确定哪些元素会被保留while (cur < n) {// 计算复写后的位置dest += (arr[cur] == 0) ? 2 : 1;// 若已达边界，停止探索if (dest >= n - 1) break;cur++;}// 处理dest越界的情况（最后一个0只能复写一次）if (dest > n - 1) {arr[n - 1] = 0;dest -= 2;cur--;}// 回填阶段：从后往前填充，避免覆盖while (cur >= 0) {if (arr[cur] != 0) {arr[dest--] = arr[cur--];} else {arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

代码走读（示例1：`[1,0,2,3,0,4,5,0]`）

前探阶段：
- cur=0（元素1）：dest从-1→0（+1），cur++
- cur=1（元素0）：dest从0→2（+2），cur++
- cur=2（元素2）：dest从2→3（+1），cur++
- cur=3（元素3）：dest从3→4（+1），cur++
- cur=4（元素0）：dest从4→6（+2），cur++
- cur=5（元素4）：dest从6→7（+1），此时dest=7等于n-1（7），停止。cur=5
边界修正：dest未越界，无需处理。
回填阶段：
- cur=5（元素4）：arr[7]=4，dest=6，cur=4
- cur=4（元素0）：arr[6]=0，arr[5]=0，dest=4，cur=3
- cur=3（元素3）：arr[4]=3，dest=3，cur=2
- 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,3,0,0,4]

复杂度分析

复杂度类型	具体值	说明
时间复杂度	O(n)	前探遍历一次+回填遍历一次，总次数为2n
空间复杂度	O(1)	仅用两个指针，原地修改

五、常见问题与解决方案

为什么dest初始化为-1？
- 因为数组索引从0开始，dest初始为-1，当遇到第一个元素时，dest+1或+2能正确指向0或1位置。如果初始为0，第一个非零元素会多占一个位置。
前探阶段为什么用dest >= n-1作为终止条件？
- 比如n=8，最大索引是7。当dest达到7时，已经填满数组，再往后的元素会被截断，所以必须停止。
边界修正的作用是什么？
- 当最后一个元素是0，且复写后dest超出数组长度（如[0,0]，dest会达到3，超过n-1=1），此时只能保留一个0在末尾，否则会越界。