283 move zeroes
283. Move Zeroes
题目: https://leetcode.com/problems/move-zeroes/
难度: Easy
思路：
思路一：暴力
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i = 0
while 0 in nums:
nums.remove(0)
i += 1
nums.extend([0]*i)
思路二：
一旦遇到不是0的就把它往前移动，移动非0完成，剩下的全部填0，看例子
0 1 0 3 12
也算双指针吧， 首先cur = 0， idx = 0，为0，不变，然后idx = 1，不为0，前移，数组变成
1 1 0 3 12
继续idx 这个时候是2，不变，继续处理,碰到3可以变成
1 3 0 3 12
这样知道变换完成，简直逆天啊，因为cur 总是小于idx，所以总可以保持这样的稳定性
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
cur,idx = 0,0
while idx < len(nums):
# cur is not 0
if nums[idx] != 0 :
nums[cur] = nums[idx]
cur += 1
idx += 1
while cur < len(nums):
nums[cur] = 0
cur += 1
思路三：
传统的双指针，参考这里
http://fisherlei.blogspot.com/2015/10/leetcode-move-zeroes-solution.html
此法最快，beats 90.50%
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
p0, p1 = 0, 0 # P1指向非0，p0指向0
while p0 < len(nums) and p1 < len(nums):
if nums[p0] != 0:
p0 += 1
p1 = p0
continue
if nums[p1] == 0:
p1 += 1
continue
nums[p0],nums[p1] = nums[p1],nums[p0]
p0 += 1
p1 += 1
相反，我觉得这样双指针反而没有上面的代码容易理解
思路四：
一个比较巧妙的方法：
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums.sort(key= lambda x: 1 if x == 0 else 0)
原理就是原先为0的数优先级在此次sort中更高了，所以全部升序排列排到后面去了
但是这个解法被人说是没有满足题目no extra space的条件，详见Sayo
timsort can require a temp array containing as many as N//2 pointers, which means as many as 2*N extra bytes on 32-bit boxes.
