283：移动零（C++）

题目地址：https://leetcode-cn.com/problems/move-zeroes/

题目描述：

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

题目示例：

示例

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

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

解题思路：

思路1：遍历数组，统计元素0的个数cnt，然后在数组后追加cnt个0。时间复杂度O(n)，空间复杂度O(n)；

思路2：双指针，定义两个指针i和j遍历数组，i和j同时向后移动，当遇到元素0时，j停止移动，i继续移动直到遇到一个非0元素，然后交换元素nums[j]和nums[i]。时间复杂度O(n)，空间复杂度O(1)。

程序源码：

思路1

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cnt = 0;
        vector<int> res;
　　　　　//step1：统计元素0个数
        for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] == 0) cnt++;
            else
                res.push_back(nums[i]);
        }
　　　　 //step2：追加元素0
        while(cnt--)
        {
            res.push_back(0);
        }
　　　　 //step3：合并step1和step2数组中的元素
        for(int i = 0; i < nums.size(); ++i)
        {
            nums[i] = res[i];
        }
    }
};

思路2

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
       int j = 0;
       for(int i = 0; i < nums.size(); ++i)
       {
           if(nums[i] != 0)
           {
               /*
               if(i != j)
               {
                  int tmp = nums[j];
                  nums[j] = nums[i];
                  nums[i] = tmp;
               }
               j++;*/
               //代码简写
               swap(nums[j++], nums[i]);
           }
       }
       //另一种style
       /* int i = 0, j = 0;
        while(i < nums.size())
        {
            if(nums[i] != 0)
            {
                swap(nums[j++], nums[i]);
            }
            i++;
        }*/
    }
};