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:

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

Solutions

1. Two Pointers

# Time: O(n)
# Space: O(1)
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i, j = 0, 0
        n = len(nums)
        while i < n and j < n:
            while i < n and nums[i] != 0:
                i += 1
            j = i
            while j < n and nums[j] == 0:
                j += 1
            if i < n and j < n and nums[i] == 0 and nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
        return nums
# 21/21 cases passed (412 ms)
# Your runtime beats 6.62 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.8 MB)

  优化版本:

# Time: O(n)
# Space: O(1)
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i_zeros = 0
        for i in range(n):
            if nums[i] != 0:
                nums[i], nums[i_zeros] = nums[i_zeros], nums[i]
                i_zeros += 1

# 21/21 cases passed (48 ms)
# Your runtime beats 75.7 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.8 MB)

References

  1. 283. Move Zeroes