0283._move_zeroes.md

283. Move Zeroes

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/move-zeroes/description/

内容描述

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

解题方案

思路 1

这个思路不符合题目意思，题目要求in-place

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)

思路 2

一旦遇到不是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

然后变成

1	3	12	3	12
            ^        ^
           cur      idx

这样知道变换完成，简直逆天啊，因为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

思路 3

传统的双指针，参考这里

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

相反，我觉得这样双指针反而没有上面的代码容易理解

思路 4

一个比较巧妙的方法：

这个思路符合题目意思in-place，但是时间复杂度是O(nlgn)

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.