【优选算法必刷100题】第001~002题（双指针算法）：移动零、复写零问题求解

艾莉丝努力练剑

发布于 2025-11-13 11:05:00

2510

文章被收录于专栏：C / C++C / C++

🔥个人主页：艾莉丝努力练剑 ❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题、洛谷刷题、C/C++基础知识知识强化补充、C/C++干货分享&学习过程记录、测试开发要点全知道、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶 🍉学习方向：C/C++方向学习者 ⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

001 移动零

力扣链接：283. 移动零

力扣题解链接：双指针求解【移动零】问题

题目描述：

1.1 思路

双指针算法——

创建两个数组，cur和dest——

cur：从左往右扫描数组，遍历数组

dest：已处理的区间内，非零元素的最后一个位置

cur往后遍历数组的过程中：

1、遇到0元素：cur++; 2、遇到非零元素：swap(nums[dest+1],nums[cur])，然后dest++,cur++。

也就是说——

算法思路： 在本题中，我们可以用一个cur指针来扫描整个数组，另一个dest指针用来记录非零数序列的最后一个位置。根据cur在扫描过程中遇到的不同的情况，分类处理，实现数组的划分。在cur遍历期间，使得[0 , dest]的元素全部都是非零元素，[dest + 1 , cur - 1]的元素都是零。

1.2 算法流程

1.2.1

初始化cur = 0（用来遍历数组），dest = -1（指向非零元素序列的最后一个位置。因为刚开始我们也不知道最后一个非零元素到底在什么位置，因此初始化为-1）

1.2.2

cur依次往后遍历每个元素，遍历到的元素会有下面两种情况：

1、遇到的元素都是0，cur直接++。因为我们的目标是让[dest + 1 , cur - 1]内的元素全都是零，因此当cur遇到0的时候，直接++，就可以让0在cur - 1的位置上，从而在[dest + 1 , cur - 1]内；

2、遇到的元素不是0，dest++，并且交换cur位置和dest位置的元素（swap），之后让cur++，扫描下一个元素。

（1）因为dest指向的位置是非零元素区间的最后一个位置，如果扫描到一个新的非零元素，那么它的位置就应该在dest + 1的位置上，因此dest先自增1；（2）dest++之后，指向的元素就是0元素（因为非零元素区间末尾的后一个元素就是0），因此可以交换到cur所处的位置上，实现[0 , dest]的元素全部都是非零元素，[dest + 1 , cur - 1]的元素都是零。

1.3 代码实现

代码演示：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
    for(int dest = -1,cur = 0;cur < nums.size();cur++)
    {
        if(nums[cur])
            swap(nums[++dest],nums[cur]);
    }
    }
};

时间复杂度：O(N)，空间复杂度：O(1)。

1.4 过程推算

本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下！

002 复写零

力扣链接：1089. 复写零

力扣题解链接：双指针算法解决【复写零】问题

题目描述：

2.1 思路

双指针算法——

先根据“异地”操作，然后优化成双指针下的“就地”操作。

1、先找到最后一个“复写”的数：双指针算法—— （1）先判断cur位置的值；（2）决定dest向后走一步还是两步；（3）判断一下dest是否已经到结束位置；（4）cur++。 2、处理一下边界情况—— 到达n-1位置，cur--，dest -= 2，复写两次0。 3、“从后往前”完成复写操作。

也就是说——

如果“从前向后”进行原地复写操作的话，由于0的出现会复写两次，导致没有复写的数会被覆盖掉。因此我们选择“从后往前”的复写策略。

但是我们选择“从后往前”的复写的时候，需要找到“最后一个复写的数”，因此我们的大体流程分两步：（1）先找到最后一个复写的数；（2）然后从后往前进行复写操作。

2.2 算法流程

2.2.1

初始化两个指针cur = 0，dest = 0；

2.2.2

找到最后一个复写的数：

1、当cur < n的时候，一直执行下面循环：

（1）判断cur位置的元素：

1）如果是0的话，dest就往后移动两位； 2）否则，dest往后移动一位。

2.2.3

判断dest是否越界到n的位置：

1、如果越界，执行以下三步：

（1）n - 1位置的值修改成0；（2）cur向前移动一步；（3）dest向前移动两步。

2.2.4

从cur位置开始往前遍历原数组，依次还原出复写后的结果数组：

1、判断cur位置的值：

（1）如果是0：dest以及dest - 1位置修改成0，dest -= 2；（2）如果非零：dest位置修改成0，dest -= 1；

2、cur--，复写下一个位置。

2.3 代码实现

代码演示：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        //1、先找到最后一个数
        int cur = 0,dest = -1,n = arr.size();
        while(cur < n)
        {
            if(arr[cur])
            {
                dest++;
            }
            else
            {
                dest += 2;
            }
            if(dest >= n - 1)
                break;
            cur++;
        }

        //2、处理边界问题
        if(dest == n)
        {
            arr[n -1] = 0;
            cur--;
            dest -= 2;
        }
        //3、从后往前完成复写操作
        while(cur >= 0)
        {
            if(arr[cur])
                arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};