LeetCode 283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

解析：

将一个数字中的所有0移到数组末尾，其他非零元素相对位置保持不变。要去原地置换，并且移动次数尽可能的少。

采用双指针法，一个指针index指向当前0的位置，另一个指针i不断往后遍历，如果当前i指向的元素非0，则将其赋值到index指向的位置。

代码1如下：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int zero_point = -1;
        //int nonzero_point = 0;
        for(int index = 0; index < len; index ++)
        {
            if(nums[index] == 0)
            {
                if(zero_point == -1)
                    zero_point = index;
            }else
            {
                if(zero_point >= 0)
                    nums[zero_point ++] = nums[index];
            }
        }
        if(zero_point >=0)
            std::fill(nums.begin()+zero_point, nums.end(), 0);
    }
};

代码2：

对上面代码进行简洁一点处理

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int index = 0;
        for(int i=0; i < len; i++)
        {
            if(nums[i] != 0)
                nums[index++] = nums[i];
        }
        for(int i = index;i<nums.size();i++){
            nums[i] = 0; 
        }
    }
};

时间和内存占用对比：