0283. Move Zeros - chasel2361/leetcode GitHub Wiki

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.

這個題目的目的是處理陣列中的 0，直接編輯輸入的陣列，將其挪到陣列尾端。

我解題的思維很單純，把陣列中的每一個項取出來看，如果是 0 就將其刪除、並在尾端加入 0，程式碼如下

[1] 可以用 for 迴圈來控制迭代的次數

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0
        for _ in range(len(nums)):  # [1]
            if nums[i] == 0:
                del nums[i]
                nums.append(0)
            else:
                i += 1

我原本迴圈的部分打算用 while i < len(nums)，但如果這樣做的話，當迴圈進行到陣列尾端全為零的部分就會停不下來，所以才使用 for 來控制迴圈次數。

這樣寫的時間複雜度是 O(N)，空間複雜度是 O(1)

---

另外，也可以使用類似 two pointer 的作法，以 i 代表現在的位置，n 代表非零尾端的位置，但核心概念以及時間/空間複雜度跟前面的做法差不多

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