Skip to content

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.


回到顶部