把零搬到後面 Move Zeroes_Leetcode 精選75題

Jeremy Perkins on Unsplash

題目敘述

題目會給定我們一個整數陣列nums，要求我們把裡面的0做元素交換，把0都搬到陣列的右邊。題目要求必須in-place在原本的陣列裡面做操作，不可以額外建立新的陣列。

題目的原文敘述

測試範例

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 <= 10^4

輸入陣列nums長度介於 1~10^4 之間。

• -2^31 <= nums[i] <= 2^31 - 1

每個元素大小介於 -2^31 ~ 2^31 - 1 之間。

演算法

其實這題用逆向思考來解可以很漂亮地解出來，程式碼也簡單好懂。

原本題目的要求是把0都搬到右邊，其實，從另一個角度切入，相當於

把全部非零的數字都搬到左邊。

有了這個想法以後，只要造一個loop從左到右去檢查每一個數字，每遇到一個非零的數字就把它放到左邊idx_of_nonzero所指向的位置即可。每搬一個數字過來，idx_of_nonzero就加1，去動態更新索引位置。

程式碼

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        
        # swapping index for nonzero numbers
        idx_of_nonzero = 0

        # scan each element
        for i in range(len(nums)):
            
            if nums[i] != 0:

                # swap non-zero number to the left-hand side
                nums[ idx_of_nonzero ], nums[i] = nums[i], nums[ idx_of_nonzero ]
                idx_of_nonzero += 1
                
        return 

關鍵知識點:

有時候題目原本的題意比較不好解的時候，可以試著逆向思考或著從不同的角度去切入，可能有意想不到的收穫喔!