【力扣】移动零，双指针法

移动零原题地址

方法一：传统双指针法

本题要求把非零元素移动到左边，零移动到右边，这跟快速排序的单趟非常相似。

定义左右指针 left 和 right ， right 指针负责探测所有元素，如果遇到非零元素，则左右指针交换，再同时右移；如果遇到零，则左指针不动，右指针右移。

说人话就是：如果遇到非零元素，就把这个数换到左边，把左边的零换到右边；如果遇到零，那就不用管了，零就该待在右边。

// 方法一：双指针
class Solution
{
public:
    void moveZeroes(vector<int>& nums)
    {
        int n = nums.size();
        int left = 0;
        int right = 0;

        // 非零，交换数据，左右指针都往右移
        // 零，右指针右移
        while (right < n)
        {
            if (nums[right])
            {
                swap(nums[left], nums[right]);
                ++left;
            }

            ++right;
        }
    }
};

方法二：双指针的取巧实现

这道题可以用另一种方式理解。我们可以考虑把所有非零数都移动到左边，再在右边填充零。

同样定义 left 和 right ， right 负责探测所有元素，如果遇到非零元素，就把这个元素覆盖到 left 的位置，两个指针同时右移；如果遇到零，左指针不动，右指针右移。

这样，我们就把所有的非零元素移动到了左边，此时只要把 left 右边的位置都用零覆盖即可。

// 方法二：双指针的另一种取巧实现
class Solution
{
public:
    void moveZeroes(vector<int>& nums)
    {
        int n = nums.size();
        int left = 0;
        int right = 0;

        // 非零，覆盖到左边
        while (right < n)
        {
            if (nums[right])
            {
                nums[left++] = nums[right];
            }

            ++right;
        }

        // 后面全填零
        while (left < n)
        {
            nums[left++] = 0;
        }
    }
};