這題 283. Move Zeroes，目標是將陣列中的所有 0 移動到陣列的末尾，並保持其他元素的相對順序不變。

題目：
給定一個陣列 nums，我們要將陣列中的所有 0 移動到末尾，且保持其他元素的順序不變。可以在原地操作，也就是不需要使用額外空間來儲存陣列。

範例：
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Input: nums = [0]
Output: [0]

Input: nums = [0,0,1]
Output: [1,0,0]

解題思路

直覺想法是遇到0就把它搬到尾巴去，但是可能會遇到i=1的0被交換到i=0去，

這樣寫的話就太沒效率了，送出後速度 981 ms 顯然是最後一名，用了兩次迴圈遍歷，

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

nums[i] 找到 0 並它移至尾巴，nums[i] !=0 時才 i++，

用一個 end 變數記住尾巴位置(也就是零有幾個 end 就往前移動幾格)

即使這樣還是要 462 ms 最後一名

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

改成針對非零者去交換0

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

這樣的解法可以達到 O(n) 的時間複雜度。

參考：
#283. Move Zeroes