LeetCode 283: 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.

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

限制條件

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

範例

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

解法一：暴力解

步驟詳解

1. 從 nums 的最末端開始遍歷整個陣列：
   1. 若當前元素不為 0，跳過該次迭代。
   2. 若否，將目前為止的右半邊子字串全部向左移一位，並在最後加上一個 0。

程式碼

def move_zeros(nums: List[int]) -> None:
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] != 0:
            continue
        else:
            for j in range(i, len(nums) - 1):
                nums[j] = nums[j + 1]
            nums[len(nums) - 1] = 0

複雜度分析

• 時間複雜度：O(N2)，其中 N 為 nums 的陣列長度。
• 空間複雜度：O(1)

解法二：雙指針

解題思路

在遍歷 nums 的過程中，如果我們可以持續追蹤每個非 0 元素應該要被插入的位置，那我們就可以使用雙指針來在一次性的遍歷過程中將非 0 元素持續往左在對應的位置插入。

步驟詳解

1. 使用雙指針 i 與 j 從頭遍歷整個陣列 nums。其中 i 指針代表的是非 0 元素會被插入的位置，j 指針則是用來尋找下一個非 0 元素。兩個指針都從位置 0 開始出發。
2. 持續移動 j 指針直到 nums 陣列末端，在遍歷過程中：
   1. 若 j 指針的當前元素為 0，繼續移動 j 指針。
   2. 若 j 指針的當前元素為非 0，將當前元素移至 i 指針的位置後，同時移動 i 與 j 指針。
3. 當 j 指針指到 nums 末端時，由於我們已經將所有非 0 元素都移至 nums 左側了，這時候就可以將 i 指針當前位置開始直到 nums 末端的所有元素全部替換成 0。

程式碼

def move_zeros(nums: List[int]) -> None:
    i, j = 0, 0

    while i <= j:
        if i == len(nums):
            break
        elif j == len(nums):
            nums[i] = 0
            i += 1
        elif nums[j] != 0:
            nums[i] = nums[j]
            i += 1
            j += 1
        else:
            j += 1

複雜度分析

• 時間複雜度：O(N)，其中 N 為 nums 的陣列長度。
• 空間複雜度：O(1)

解法三：遍歷計數

解題思路

從範例中我們可以觀察到，在整個 nums 進行完移動後，每一個非 0 的元素都會向左移動一段距離，而這個距離正好是到當前元素為止的 0 的總量。因此，我們可以利用這個特性，在遍歷的過程中持續計算目前遇過 0 的總量，並將每個非 0 元素移動至對應的位置。

步驟詳解

1. 初始化一個變數 zero_count 來作為統計目前為止所有遍歷過的 0 數量。
2. 第一次遍歷：
   1. 如果遇到 0，將 zero_count 遞增 1。
   2. 如果遇到非 0 元素，將當前元素向左平移 zero_count 個位置。
3. 第二次遍歷：
   1. 將從 len(nums) - zero_count 直到 nums 陣列末段的元素全部替換為 0。

程式碼

def move_zeroes(nums: List[int]) -> None:
    zero_count = 0
    for i, num in enumerate(nums):
        if num == 0:
            zero_count += 1
        else:
            nums[i - zero_count] = num

    for i in range(len(nums) - zero_count, len(nums)):
        nums[i] = 0

複雜度分析

• 時間複雜度：O(N)，其中 N 為 nums 的陣列長度。
• 空間複雜度：O(1)

參考資料

• LeetCode 原題出處：Move Zeroes – LeetCode