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元素移到数组末尾，同时保证其他元素的相对顺序不变，并且要求in-place和尽量少的操作。
我的思路是首先找0元素，然后在0后面找第一个非0元素，交换它们，直到数组末尾。完整代码如下：

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

本代码提交AC，用时46MS。

后来在网上看了看别人的解法，发现只需要一遍循环就可以，而且代码非常简洁，真是太棒了。
思路是找非0元素，然后和之前的元素交换，但是之前的元素（下标j对应元素）不一定是0，因为只有非0时才交换，所以交换次数是非0元的个数。
完整代码如下：

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

本代码提交AC，用时13MS，果然快了不少。

二刷。简单方法，两个指针，j指针一直往前走，i指针指向当前可以填入非0元素的位置。j扫完之后，i后面的都应该是0。

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

本代码提交AC，用时12MS。