283.move_zeroes.md

283. Move Zeroes 难度 简单

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

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

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

Example 2:

Input: nums = [0] Output: [0]

Constraints:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

相关企业

• Facebook|19
• 微软 Microsoft|14
• 亚马逊 Amazon|11
• 苹果 Apple|9
• 字节跳动|8

相关标签

• Array
• Two Pointers

相似题目

• Remove Element 简单

提示1

In-place means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.

提示2

A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

2 ways to ask

if don't need to maintain the relative order of non-zero elements in original array

• Best solution: partition

if need to maintain the relative order of non-zero elements in original array (This question)

• Best solution: fast & slow 2 pointers

Not that good solution. O(n) but more write operations. Easier to understand.

python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        
        slow, fast = 0, 0
        while fast <= len(nums) - 1:
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
            fast += 1

Better solution. O(n) guarantee least write operation

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return
        
        slow, fast = 0, 0
        while fast <= len(nums) - 1:
            if nums[fast] != 0:
                nums[slow] = nums[fast] 
                slow += 1
            fast += 1
            
        while slow < len(nums):
            if nums[slow] != 0:
                nums[slow] = 0
            slow += 1