【leetcode初级】8-移动0

• 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
  说明:
  必须在原数组上操作，不能拷贝额外的数组。
  尽量减少操作次数。

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

• 思路：
  不能拷贝额外数组空间的话，就只能在原数组上移动。通过一个指针从头对数组进行遍历，如果是非0的数，就把它赋值到第一个位置（相当于新建一个数组的第一个位置），不断的去赋值。这样可以得到一个前半段是我们想要的非零数组。在遍历过程中我们统计0的数目，然后在非零段后面去添加该数目个0,即得到新数组。总的来说思路和新建一个数组是类似的，但要转换一下思维。两者时间复杂度都是O(n)，但前者就可以将空间复杂度降到O(1)。
• 代码：

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = 0 #fast point
        j = 0 #slow point
        zero_count = 0
        while i < len(nums):
            if nums[i] != 0:
                nums[j] = nums[i]
                j += 1
            else:
                zero_count += 1
            i += 1
        for x in range(zero_count):
            nums[j] = 0
            j += 1

• 这个算法可以说非常快了，44ms超过了99%的提交者。