283. Moving Zeros 经典数组问题的三个解法

题目描述见　https://leetcode.com/problems/move-zeroes/

方法一

非in-place算法：
首先数一下数组中有多少个０　（遍历一次）
然后把数组中非零元素复制到templist中（遍历一次）
然后把templist尾部填充０，
最后把templist覆盖到nums.

时间复杂度：O(n)
空间复杂度：O(n)

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        # method 1
        numzeros = 0
        n = len(nums)
        
        for ele in nums:
            if not ele:
                numzeros +=1
        
        templist = []
        for ele in nums:
            if ele:
                templist.append(ele)
        
        while numzeros:
            templist.append(0)
            numzeros -=1
            
        nums[:] = templist[:]

方法二

遍历nums，如果遇到非零元素就位置０开始复制到nums前面．使用一个指针标记复制序列的尾部．

时间复杂度：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.
        """
        
        # method 2
        pivot = 0
        
        for ele in nums:
            if ele:
                nums[pivot] = ele
                pivot +=1
        
        while pivot < len(nums):
            nums[pivot] = 0
            pivot +=1

方法三

维持两个指针p1 和 p2，其中p1是从nums[0]开始的非零序列的尾部．从头遍历数组，如果遇到非零元素就将它和前面p1指向的元素交换．由于存在零，最后自然把０都移到了数组末尾．

时间复杂度：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.
        """
        
        # method ３
        pivot1 = 0
        pivot2 = 0
        
        while pivot2 < len(nums):
            if nums[pivot2]:
                #swap nums[p1] and nums[p2]
                temp = nums[pivot1]
                nums[pivot1] = nums[pivot2]
                nums[pivot2] = temp
                pivot1 +=1
            pivot2 +=1