0283._move_zeroes.md

Navigation

• Navigation
• Links
• Solution 1 timsort
• Solution 2 双指针，覆盖(赋值)后填充0
• Solution 双指针，交换

Links

1. https://leetcode.com/problems/move-zeroes
2. https://leetcode-cn.com/problems/move-zeroes/

Solution 1 timsort

    时间复杂度：O(NlogN)
    空间复杂度：O(N)

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        nums.sort(key=lambda x: 1 if x == 0 else 0)

Solution 2 双指针，覆盖(赋值)后填充0

1. 遍历数组，把非0的数字覆盖(赋值)到数组的前面的位置
2. 移动完毕，在数组的后面的位置补充0

    时间复杂度：O(N)。
    空间复杂度：O(1)

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        slow = 0
        fast = 0
        length = len(nums)

        while fast < length:
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
            
            fast += 1

        while slow < length:
            nums[slow] = 0
            slow += 1

---

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        last_none_zero_index = 0    # 慢指针

        for num in nums:    # 快指针，比慢指针快或者在相等的位置。python for loop 隐藏了指针。
            if num != 0:
                nums[last_none_zero_index] = num
                last_none_zero_index += 1

        last_zero_index = last_none_zero_index

        while last_zero_index < len(nums):
            nums[last_zero_index] = 0   
            last_zero_index += 1

---

Go

package main

func moveZeroes(nums []int) {
	slow := 0
	n := len(nums)

	for _, num := range nums {
		if num != 0 {
			nums[slow] = num
			slow++
		}
	}

	for ; slow < n; slow++ {
		nums[slow] = 0
	}
}

Solution 双指针，交换

    时间复杂度：O(N)
    空间复杂度：O(1)

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        slow = 0
        
        for index, value in enumerate(nums):
            if value != 0:
                nums[slow], nums[index] = nums[index], nums[slow]
                slow += 1

---

Go

package main

func moveZeroes(nums []int) {
	slow := 0

	for i, num := range nums {
		if num != 0 {
			nums[slow], nums[i] = nums[i], nums[slow]
			slow++
		}
	}
}

---

Go

func moveZeroes(nums []int) {
    left, right, n := 0, 0, len(nums)
    for right < n {
        if nums[right] != 0 {
            nums[left], nums[right] = nums[right], nums[left]
            left++
        }
        right++
    }
}