LeetCode 1089. 复写零

2022-09-08 HGNULB 约 11 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 1089. 复写零

题意分析

给定一个定长数组，要求把其中每一个 0 都写成两个 0，其余元素原样保留，整体向右挤压，超出数组长度的部分直接丢弃。数组长度固定不变，也不需要返回任何东西，所有修改必须直接作用在传入的数组上。

约束里最关键的一句是「不要在超过该数组长度的位置写入元素」，配合「就地修改，不要返回任何东西」，等于明确禁止了申请一个新数组再拷回来的做法，把空间限制在常数级。这是一个很强的信号：既然不能借助额外空间缓冲，就必须找到一种写入顺序，使得每次写入的目标位置上的旧值要么已经被读过、要么根本不再需要。数组长度上限只有一万，时间上完全没有压力，题目的全部难度都集中在「原地」这两个字上。

边界集中在数组尾部。最容易忽略的一种情况是：最后一个被保留下来的元素恰好是 0，但数组只剩一个空位，此时只能写下这个 0 的第一份，第二份必须被截断丢弃。另外还有全是 0 的数组（结果仍是全 0，但每个 0 的来源发生了错位）、完全没有 0 的数组（数组应当原封不动）以及长度为 1 的数组这几种退化情形。

解法：双指针从后向前写入

核心思路

最朴素的做法是从左往右扫，遇到 0 就把它右边的所有元素整体后移一位再补一个 0。它是对的，但每遇到一个 0 就要搬动一整段后缀，最坏情况（数组全是 0）退化到 $O(n^2)$。另一种朴素做法是新开一个数组按规则填，填满 $n$ 个位置就停，再整体拷回原数组，这个是 $O(n)$ 时间，但用了 $O(n)$ 额外空间，被题目的原地要求直接否掉。

瓶颈在于「从左往右写」这个方向本身。向左边写入时，目标位置的旧值往往还没被读取，一写就丢，所以只能靠搬移来腾地方。观察一下这个变换的性质会发现，它是一个单调向右的挤压：任何元素在结果里的下标都不小于它在原数组里的下标。这就意味着如果反过来从右往左写，写入位置永远在读取位置的右侧或与之重合，而右侧的旧值在结果里已经用不上了（它们要么被挤出数组，要么早已被写过），覆盖它们完全安全。

于是把整个过程拆成两趟。第一趟不做任何写入，只用来确定「原数组的前多少个元素能被塞进结果里」；第二趟从这个分界点开始，倒着把元素搬到它们的最终位置上。第一趟的不变量是：用 i 指向正在考察的原数组元素，j 表示「前 i 个元素展开后一共占用多少个格子」，每读一个元素就令 j += (arr[i] == 0 ? 2 : 1)，循环在 j >= n 时停下，此时 i 恰好指向第一个装不下的元素的下一位。第二趟的不变量是：i 指向待搬运的原元素，j 指向它在结果中的落脚位置，恒有「arr[0..i] 展开后的总长度等于 j+1」，因此 j 永远不小于 i，写入不会破坏尚未读取的数据。

还有一个必须提前想清楚的细节：第一趟结束时 j 可能等于 n，也可能等于 n+1。后者发生在最后一个能进入结果的元素是 0 而只剩一个空位时——它的两份被算了 2 个格子，实际只放得下 1 个。所以第二趟写入前要对每个目标下标做一次 j < n 的检查，越界就跳过写入但照常推进指针，这样那被截断的一份自然就被丢弃了，不需要为这种情况单开分支。

解题步骤

第一趟用 i 和 j 同时从 0 出发，循环条件是 j < n。每轮先看 arr[i] 是不是 0，是就 j += 2，否则 j += 1，然后 i++。为什么循环条件挂在 j 而不是 i 上：我们要找的是「结果空间被填满」的时刻，而不是「原数组被读完」的时刻，前者才是分界点的定义。顺带一提，由于 j 每轮至少加 1 而 i 每轮恰好加 1，恒有 i <= j < n，所以 arr[i] 的读取永远不会越界，不需要额外的下标保护。

循环结束后执行 i-- 和 j--。原因是循环退出时 i 已经越过了最后一个被采纳的元素，j 也已经越过了结果的最后一格，两者都需要回退一步才能指向真正的「最后一个待搬运元素」和「它的落脚位置」。注意 j 回退后可能仍等于 n，这正是上面说的截断情形。

第二趟循环条件是 i >= 0，每轮做三件事：把 arr[i] 写到 arr[j]（前提是 j < n）；如果 arr[i] 是 0，就再 j-- 并写一个 0（同样要 j < n 才写）；最后 i--、j-- 同时后退一格。

那两处 if (j < n) 是这个解法的安全网。它把「最后一份被截断」这个特殊情况变成了普通情况的自然结果：指针照常推进，只是写入被静默丢弃，后续所有下标关系保持不变。如果改用「先判断 j == n 再特殊处理」的写法，就要在两个位置分别讨论，代码长一倍且容易漏。

写 0 时的顺序必须是「先写第一份到当前 j，再 j-- 写第二份」。因为倒着走时，j 上的那一格对应的是这个 0 在结果里靠右的那一份，j-1 才是靠左的那一份，写反了对全 0 数组看不出差别，但只要 0 的两侧有别的元素就会错位。

第二趟自然结束时数组已被完整改写，函数无需返回值，题目要求的就地修改已经完成。

以 arr = [1,0,2,3,0,4,5,0] 走一遍，n = 8。第一趟：i=0,j=0，arr[0]=1 非零，j=1、i=1；arr[1]=0，j=3、i=2；arr[2]=2，j=4、i=3；arr[3]=3，j=5、i=4；arr[4]=0，j=7、i=5；arr[5]=4，j=8、i=6，此时 j=8 不再小于 n，循环结束。执行 i--、j-- 后 i=5、j=7，含义是「原数组前 6 个元素（下标 0 到 5）能塞进结果，其中最后一个是 arr[5]=4，它落在结果的下标 7」。第二趟：i=5,j=7，arr[7]=arr[5]=4，非零，退到 i=4,j=6；arr[6]=arr[4]=0，是零，j 退到 5 并写 arr[5]=0，再退到 i=3,j=4；arr[4]=arr[3]=3，退到 i=2,j=3；arr[3]=arr[2]=2，退到 i=1,j=2；arr[2]=arr[1]=0，是零，j 退到 1 并写 arr[1]=0，再退到 i=0,j=0；arr[0]=arr[0]=1，退到 i=-1，循环结束。最终数组是 [1,0,0,2,3,0,0,4]，原来的 5 和最后那个 0 被挤出数组，符合预期。再快速看一眼截断情形 arr = [0,0,0]：第一趟结束时 i=2、j=4，回退后 i=1、j=3，第二趟第一轮 j=3 不小于 n=3，第一份写入被跳过，随后 j 退到 2 并写 arr[2]=0，正是那个只放得下一份的 0。

代码实现

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)$，其中 $n$ 为数组长度。两趟循环各自的指针都是单向推进且不回头，第一趟 i 从 0 走到分界点，第二趟 i 从分界点走回 0，合计不超过 $2n$ 次操作。

空间复杂度：$O(1)$，凭的是全程只用了 n、i、j 三个整型变量，所有数据都写在原数组上，没有任何与规模相关的辅助结构。

关键点总结

原地改写数组时，写入方向由「元素位移的方向」决定：元素整体右移就从右往左写，整体左移就从左往右写。这样写指针永远落在读指针「已经不需要」的那一侧，覆盖才安全，这条规律可以直接迁移到合并有序数组、原地插入、原地删除等一整类题。

当写入需要知道「最终布局」才能定位时，就先跑一趟只计数不写入的预扫描。用一趟扫描换来第二趟的确定性，比边扫边猜位置再回头修补要可靠得多。

把截断、越界这类特例转化成「照常推进指针，只是跳过写入」的统一形式，能显著减少分支。判断条件写成 if (j < n) 而不是提前对 j == n 做特殊处理，是这道题代码能保持简短的关键。

倒序写一个被复制的元素时，两份的写入顺序有讲究：先写右边那份再写左边那份。对全 0 数组这个顺序看不出问题，所以自测时一定要用 0 与非 0 混排的用例。

面试视角上，这题被问到时应该主动点破「不能开新数组」这条约束才是题眼，并且解释清楚为什么从后往前写是安全的（写指针不小于读指针）。如果只给出前移搬运的 $O(n^2)$ 解法，即使通过也会被追问优化；能当场说出「先算长度再倒着填」这个两趟框架，基本就是面试官期待的答案。

易错点总结

错误写法：只写第二趟，直接从数组末尾倒着填而不先跑计数那一趟。用例 [1,0,2,3,0,4,5,0] 根本无法确定 arr[5]=4 该落在下标 7，写出来的元素整体错位，结果面目全非。

错误写法：第一趟循环条件写成 while (i < n)。用例 [1,0,2,3,0,4,5,0] 会把全部 8 个元素都算进去，j 冲到 11，分界点算错，第二趟从一个不存在的位置开始回填，元素大面积丢失。

错误写法：第一趟结束后忘记 i-- 和 j--。用例 [1,0,2,3,0,4,5,0] 会以 i=6、j=8 起步，第一轮就去读 arr[6]=5——这个元素本该被挤出数组——把它当成最后一个保留元素，结果整体右移一位且末尾数据错误。

错误写法：只写了 i-- 而漏掉 j--（或反之）。用例 [1,0,2] 会让两个指针的对应关系整体偏移一格，输出 [1,0,0] 之外的错位结果，且偏移量在遇到 0 时还会继续放大。

错误写法：第二趟去掉 if (j < n) 保护直接写 arr[j] = arr[i]。用例 [0,0,0] 第一轮的 j 等于 3，写入立刻抛出数组下标越界异常。

错误写法：写 0 时只在第二份上加 j < n 判断，第一份不判断。用例 [1,1,0]，第一趟结束 j 为 4、回退到 3，第一轮就会在下标 3 处写入而越界。

错误写法：把复写 0 的顺序写反，先 j-- 再把 arr[i] 写到 arr[j]。用例 [1,0,2,3,0,4,5,0] 会把 0 的两份都往左挪一格，输出 [0,0,1,2,3,0,0,4] 这类首元素被污染的结果。

错误写法：第二趟的循环条件写成 while (j >= 0)。用例 [1,2,3] 里 i 会先于 j 减到 -1，随后 arr[i] 读到负下标，抛出越界异常。

错误写法：新开一个 int[] tmp = new int[n] 按规则填好再 System.arraycopy 回去。用例是任意输入，结果虽然正确，但违背题目「就地修改、空间 $O(1)$」的要求，面试里会被判定为没答到点上。

错误写法：从左往右遇到 0 就用 System.arraycopy 把后缀整体右移一位。用例 [0,0,0,...,0]（一万个 0）会做近一万次长度递减的整段搬移，运行时间退化到平方级别，在大数据点上超时。

相似题目

题目	难度	考察点
26. 删除有序数组中的重复项	简单	数据整体左移，读写指针同向且写指针永远落后于读指针
27. 移除元素	简单	不要求保序时可以用尾部元素直接顶替待删位置
75. 颜色分类	中等	三个指针把数组切成四段，交换后中间指针是否前进要分类讨论
80. 删除有序数组中的重复项 II	中等	保留至多两次，判断依据是写指针回看两格而非比较相邻元素
88. 合并两个有序数组	简单	与本题最同构，同样靠从后往前写来避免覆盖未读数据
283. 移动零	简单	零向右挤而非复制，非零元素前移后需要把尾部清零
344. 反转字符串	简单	对撞指针原地交换，读写在同一步完成，不存在覆盖问题
443. 压缩字符串	中等	结果比原串短，写指针在左侧追读指针，还要处理多位数字
977. 有序数组的平方	简单	从两端向中间取最大值，倒着填充结果数组
剑指 Offer 05. 替换空格	简单	扩张型替换，先算目标长度再从后往前填，与本题思路一致
面试题 01.03. URL化	简单	给定真实长度而非整个缓冲区长度，起点定位是主要陷阱