LeetCode 原地复写零：双指针与逆向填充的 O(n) 解法

三、代码实现

class Solution {
    public void duplicateZeros(int[] arr) {
        int cur = 0, pre = -1, n = arr.length;
        
        // 1. 找到要复写的最后一个元素
        while (cur < n) {
            if (arr[cur] == 0) {
                pre += 2;
            } else {
                pre++;
            }
            if (pre >= n - 1) {
                break;
            }
            cur++;
        }
        
        // 处理边界情况：如果 pre == n，说明最后一个元素是 0 且刚好占满最后一位
        if (pre == n) {
            arr[n - 1] = 0;
            cur--;
            pre -= 2;
        }
        
        // 2. 开始从后向前复写
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[pre--] = arr[cur--];
            } else {
                arr[pre--] = 0;
                arr[pre--] = 0;
                cur--;
            }
        }
    }
}

四、复杂度分析

• 时间复杂度 O(n)：只需要遍历数组两次，第一次定位边界，第二次逆向填充。
• 空间复杂度 O(1)：使用的原数组，没有额外分配空间。

五、总结

本解法通过双指针先定位复写边界，再逆向填充数组，既避免了正向遍历的元素覆盖问题，又实现了 O(n) 线性时间复杂度与 O(1) 常数空间复杂度的最优表现。其中'先确定边界、再逆向操作'的思路，是解决数组原地修改类问题的关键技巧，具有较强的通用性与实用性。