Move Zeroes

Given an arraynums, write a function to move all0's to the end of it while maintaining the relative order of the non-zero elements.

For example, givennums = [0, 1, 0, 3, 12], after calling your function,numsshould be[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.

题目大意：

给定一个数组nums，编写函数将数组内所有0元素移至数组末尾，并保持非0元素相对顺序不变。

例如，给定nums = [0, 1, 0, 3, 12]，调用函数完毕后， nums应该是 [1, 3, 12, 0, 0]。

注意：

1. 你应该“就地”完成此操作，不要复制数组。

2. 最小化操作总数。

解题思路：

题目可以在O(n)时间复杂度内求解

算法步骤：

这道题让我们将一个给定数组中所有的0都移到后面，把非零数前移，要求不能改变非零数的相对应的位置关系，而且不能拷贝额外的数组，那么只能用替换法in-place来做，需要用两个指针，i is index of first zero，j is the index of first non-zero item after index i, 然后i 和 j 交换位置即可

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in xrange(len(nums)):
            if nums[i] != 0:
                nums[j], nums[i] = nums[i], nums[j]
                j += 1    //j+1也一定是第一个为0的element的系数

array index ->         0     1     2     3     4     5     6     7     8
after iter #0: z=0 [ 0_1,    4,    6,  7_1,  0_2,  0_3,    7,  0_4,    9]
after iter #1: z=1 [   4,  0_1,    6,  7_1,  0_2,  0_3,  7_2,  0_4,    9] [1]4 <-> [0]0_1
after iter #2: z=2 [   4,    6,  0_1,  7_1,  0_2,  0_3,  7_2,  0_4,    9] [2]6 <-> [1]0_1
after iter #3: z=3 [   4,    6,  7_1,  0_1,  0_2,  0_3,  7_2,  0_4,    9] [3]7 <-> [2]0_1
after iter #4: z=3 [   4,    6,  7_1,  0_1,  0_2,  0_3,  7_2,  0_4,    9]
after iter #5: z=3 [   4,    6,  7_1,  0_1,  0_2,  0_3,  7_2,  0_4,    9]
after iter #6: z=4 [   4,    6,  7_1,  7_2,  0_2,  0_3,  0_1,  0_4,    9] [6]7 <-> [3]0_1
after iter #7: z=4 [   4,    6,  7_1,  7_2,  0_2,  0_3,  0_1,  0_4,    9]
after iter #8: z=5 [   4,    6,  7_1,  7_2,    9,  0_3,  0_1,  0_4,  0_2] [8]9 <-> [4]0_2