LeetCode 1089. 复写零
题目描述
题意分析
把原数组中的每个零连续写两份，非零元素写一份，只保留展开后最前面的 $n$ 个元素。数组长度不能改变，需要直接修改原数组。
展开会把元素向右移动，从左往右直接写入可能覆盖尚未读取的原值。先确定哪些原元素会留在结果里，再从后往前回填，就能让写入发生在已经不需要读取的右侧。
解法：双指针从后向前写入
核心思路
[!blue]
第一趟中，
i是已统计的原元素个数，j是这些元素复写后的虚拟长度。非零使j增加一，零使它增加二；直到j >= n时停止。此前每个元素至少贡献一格，所以i <= j，统计过程不会提前读出数组范围。此时找到的原前缀已经足够填满结果，后面的原元素都会落在结果范围之外，可以不再处理。将
i、j各减一，把计数转为下标：i指向尚未回填的最后一个原元素，j指向它展开后的最后一个位置。回填时先将原值写到
j，若原值为零，再把左边一格也写成零，然后一起向左推进。剩余前缀展开后不会更短，所以始终有j >= i；原值为零时还多占一格，有j >= i+1。因此两次写入都不会覆盖i左侧的未读数据，读取后再判断是否为零也安全。第一趟的长度最多超过 $n$ 一格，恰好对应末尾的零只有第一份能留下。回填每一份前检查
j < n，越界时只略过写入，仍移动虚拟下标；这样保留下来的各值与完整展开数组的前 $n$ 位完全一致。
解题步骤
- 前向累计非零占一格、零占两格，达到数组长度后停止。
- 读写下标各退一位。
- 倒序复制，零写两份，每次写前检查上界。
代码实现
class Solution {
public void duplicateZeros(int[] arr) {
int n = arr.length;
int i = 0;
int j = 0;
// 只统计展开长度，先找到足以填满结果的原前缀。
while (j < n) {
if (arr[i] == 0) {
j += 2;
} else {
j += 1;
}
i++;
}
i--;
j--;
// 从后向前回填，右侧旧值已不再需要。
while (i >= 0) {
// 虚拟位置可能越过数组末尾，只跳过该次写入。
if (j < n) {
arr[j] = arr[i];
}
if (arr[i] == 0) {
j--;
// 虚拟位置可能越过数组末尾，只跳过该次写入。
if (j < n) {
arr[j] = 0;
}
}
i--;
j--;
}
}
}
func duplicateZeros(arr []int) {
n := len(arr)
i, j := 0, 0
// 只统计展开长度，先找到足以填满结果的原前缀。
for j < n {
if arr[i] == 0 {
j += 2
} else {
j += 1
}
i++
}
i--
j--
// 从后向前回填，右侧旧值已不再需要。
for i >= 0 {
// 虚拟位置可能越过数组末尾，只跳过该次写入。
if j < n {
arr[j] = arr[i]
}
if arr[i] == 0 {
j--
// 虚拟位置可能越过数组末尾，只跳过该次写入。
if j < n {
arr[j] = 0
}
}
i--
j--
}
}
复杂度分析
- 时间复杂度：$O(n)$，计数与回填各一次。
- 空间复杂度：$O(1)$，只使用读写下标。
关键点总结
[!green]
- 第一趟的写位置是虚拟长度，可能比数组多一。
- 越界跳过的是写入，不是这个元素对应的指针推进。
易错点总结
[!yellow]
- 从左向右直接覆盖，会丢失后面还需要的原值。
- 计数结束后没有把长度转成末下标，整体位置会偏一。
- 虚拟写位置不检查上界，尾部零截断时会越界。
- 无零时读写下标重合，数组保持不变；全零或只有一个零时，同一套截断规则也能填满结果，不必另写分支。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 27. 移除元素 | 简单 | 原题向前压缩要保留的元素，本题向后填充扩张后的虚拟位置，防止覆盖未读数据。 |
| 88. 合并两个有序数组 | 简单 | 同样在固定数组中从后向前写入，避免扩张或合并时破坏尚未读取的内容。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！