【双指针】复写零

原创

lirendada

发布于 2026-10-14 09:19:46

340

文章被收录于专栏：优选算法（干碎面食馆）优选算法（干碎面食馆）

1089. 复写零

1089. 复写零

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

1 <= arr.length <= 104
0 <= arr[i] <= 9

解题思路一：暴力破解

这里的暴力破解，其实也是算双指针做法，但是因为我们没有很好的利用双指针的特性，就会变成暴力破解的方式，但是这是一种比较好想到的解法，虽说时间复杂度达到了 O(n^2) 哈哈，这里看个意思就行！

其实就是我们去从头遍历数组的时候，一遇到了零，就在数组末尾从后往前将元素往后移动一位，所以时间复杂度才很高！

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        while(cur < arr.size())
        {
            int dest = arr.size() - 2;
            if(arr[cur] == 0)
            {
                // 遇到0就让dest从后往前将元素后移
                while(dest >= cur)
                {
                    arr[dest + 1] = arr[dest];
                    dest--;
                }
                cur += 2;
            }
            else
                cur++;
        }
    }
};

💥解题思路二：双指针

算法思路

其实上面这种解法之所以变成了暴力破解，其实是因为我们没办法做到一次性的去往后移动那些元素，如果遇到比较棘手的样例比如说全0，那么时间复杂度是非常高的！

但是上面的思想，也就是从后往前复写是正确的，如果我们是从前往后复写的话，那么就会导致后面元素先被覆盖就不见了！

所以我们最后还是得从后往前去遍历，也就是说我们要想办法在从后往前复写元素的时候，能一步到位！

如上图所示，其实我们只需要找到最后一个复写的数也就是上面的 4 的位置，然后再用另一个指针指向最后一个元素 0，此时直接复写，就能一次到位啦！所以我们的算法过程分为以下两步：

先找到最后一个复写的数
然后从后往前进行复写操作

算法流程

初始化两个指针 cur = 0，dest = -1
找最后一个复写的数
- 若 arr[cur] != 0，则说明不需要复写，此时 cur++，dest++ 即可！
- 若 arr[cur] == 0，说明该位置需要复写，此时要让 dest += 2，而 cur++ 即可！
- 重复上述判断直到 dest 遍历结束为止！

3. 此时不能直接复写，因为 dest 有可能不在数组内，需要做些处理：

如下图所示的情况，其实就是因为 dest 还差一步就结束了，而此时 cur 刚刚好遇到的是 0，此时 dest 多走了一步，就出界了！

4.从后往前进行复写操作

若 arr[cur] == 0，则说明要复写，将 arr[dest] 以及 arr[dest - 1] 置为 0，然后 dest -= 2
若 arr[cur] != 0，则说明不需要复写，只需要让 arr[dest] 修改为 arr[cur]，然后 dest-- 即可！
而对于 cur 来说，一直 cur-- 即可！

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1;

        // 找到最后一个复写的数字
        while(cur < arr.size())
        {
            if(arr[cur] == 0)
                dest += 2;
            else    
                dest++;
            
            if(dest >= arr.size() - 1) // 如果到达数组末尾或者出界则break
                break;
            cur++;
        }

        // 对dest出界情况进行处理
        if(dest == arr.size())
        {
            arr[arr.size() - 1] = 0;
            cur--;
            dest -= 2;
        }

        // 从后往前复写
        while(cur >= 0)
        {
            if(arr[cur] == 0)
            {
                arr[dest] = arr[dest - 1] = 0;
                dest -= 2;
            }
            else
            {
                arr[dest--] = arr[cur];
            }
            cur--;
        }
    }
};

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

指针

算法