Leetcode热题——移动零

一，题目

https://leetcode.cn/problems/move-zeroes/submissions/594915685

其实就是考察随机快排那部分知识点。

二，答案

1，逐个交换（类似冒泡法）

准备两个函数，一个负责交换向量元素位置，一个负责将非零元素向前移动（最初我是想将0往后移，发现如果在移动过程中遇到0有点麻烦，所以转换思路改为移动非零元素）

代码

class Solution {
public:
    void swap(int& a,int& b)
    {
        int x = a;
        a = b;
        b = x;
    }

    void moveHead(vector<int>& nums,int i)
    {
        while(i >= 1)
        {
            if(nums[i - 1])break;
            else swap(nums[i - 1],nums[i--]);
        }
    }
    void moveZeroes(vector<int>& nums)
    {
        for(int i = 0;i < nums.size();i++)
        {
            if(nums[i]) moveHead(nums,i);
        }
    }
};

效果

2，双指针

我的思路是直接赋值将非零数拷贝到向量前面，记录0的个数，最后将最后几个全部变为0就行了。

代码

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
        int count = 0;
        int first = 0;
        int index = 0;
        int len = nums.size();
        while(index < len)
        {
            if(nums[index]) nums[first++] = nums[index];
            else count++;
            index++;
        }

        for(int i = 1;i <= count;i++)
        {
            nums[len - count - 1 + i] = 0;
        }
    }
};

效果

3,标准答案

class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 方法二 ： 前后指针的快排思想
        int prv = -1, cur = 0;
        while (cur < nums.size())
        {
            if(nums[cur] != 0)
            {
                swap(nums[++prv], nums[cur]);
            }
            cur++;
        }
    }
};