LeetCode 283. 移动零

移动零

题目链接 283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

题目解释

这道题目的意思是我们将所有的0都移动到数组的后面,非零的元素放在前面.不过我们在移动的时候是不能够改变我们的非零元素的相对的位置的.

算法原理

这里我们可以很容易想到一个解法,我们新开辟一个数组,遍历一下我们原来的数组,如果不是零,就添加.最后将0放在我们数组的后面就可以了,下面是我们基本的想法.

vector<int> new_arr(num.size(), 0);
int index = 0;
for(i = 0; i < num.size(); ++i)
{
    if(num[i] != 0) new_arr[index++] = num[i];
}

但是,这里我们使用了一个另外的空间,不太符合题意.但是这里我们得到一个想法,下面是两个数组.

指针p1是一定不会小于p2的,那么此时我们是否可以这样想,我们让p2也是指向arr,将p1遇到的各个情况经过分析,然后赋值到p2

• p1 指向的位置是 0
• p1 指向的位置非 0

对于p1 非0,那么我们直接赋值,然后让p1和p2 分别自增.如果我们遇到p1是0了,那么我们不关心,让p1自增.

细节补充

这里我们谈两个

• 我们循环的条件,按照我们的原本的想法,p1是小于我们的arr的长度的
• 当我们循环结束后,是否是立即返回?不是的,我们需要将p2位置和后面都赋值给0.

代码编写

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int fast = 0;
        int slow = 0;
        while(fast < nums.size())
        {
            if(nums[fast] != 0)
            {
                nums[slow++] = nums[fast];
            }
            fast++;
        }
        while(slow < nums.size())
        {
            nums[slow++] = 0;
        }
    }
};