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

示例:

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

说明:

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

Solution

• 利用冒泡排序的思想，不过时间复杂度有点高。
• 从后往前遍历，如果nums[i]为 0，再看其后一个元素，nums[i+1] 不为0，则进行交换，直到后一个数为 0.

# @lc code=start
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-2, -1, -1):
            if nums[i] == 0:
                for j in range(i, len(nums)-1):
                    if nums[j+1] != 0:
                        nums[j], nums[j+1] = nums[j+1], nums[j]
                        
# @lc code=end

@yuan-zi-17

• 利用快慢指针。
• 快指针不断往后遍历，找到不为0的数，一旦找到，就把该值赋予给慢指针所在的位置，然后慢指针往后走一格，这样就保证慢指针前面的全是非0。
• 等快指针遍历完了，那么直接把慢指针之后的都赋为0即可。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return 0
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        for i in range(slow, len(nums)):
            nums[i] = 0

c++

• 朴素解法，利用新数组存储非 0 元素
• 时间复杂度 O(n)，空间复杂度 O(n)

// @lc code=start
class Solution {
public:
    void moveZeroes(vector<int> &nums) {
        vector<int> nonZeros;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]) {
                nonZeros.push_back(nums[i]);
            }
        }
        for (int i = 0; i < nonZeros.size(); ++i) {
            nums[i] = nonZeros[i];
        }
        for (int i = nonZeros.size(); i < nums.size(); ++i) {
            nums[i] = 0;
        }
    }
};
// @lc code=end

• 原地交换
• 时间复杂度 O(n)，空间复杂度 O(1)

class Solution {
public:
    void moveZeroes(vector<int> &nums) {
        int k = 0;  // nums[0...k-1] 都为非0元素
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]){
                swap(nums[i], nums[k]);
                k++;
            }
        }
    }
};