[LeetCode] 283. Move Zeroes

前言

　　這題題目要設法將陣列中的非零元素全部往前移，題目要求不能配置新的空間，所以不能使用輔助的 Array，那我們就由本身的陣列來做循環添加，這是比較簡單的方法，需用到一層迴圈，時間複雜度推估可達 O(n)，這裡有 JAVA 和 Python 的寫法。

題目

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.

給定一個整數陣列為 nums，移動全部的零元素到最後面，同時維持非零元素的原本順序。
注意你必須在當前陣列做，不能複製一個陣列來做。

題目連結：https://leetcode.com/problems/move-zeroes/

題目限制

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

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

範例

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

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

思路&筆記

題目要求不能配置新的空間，所以不能用輔助的 Array，那我們就由本身陣列來做循環添加。

把非零元素加到當前陣列裡

從陣列的最前面開始添加，索引從 0 開始 (從陣列的最前面)

再把當前的陣列後面補 0 即可，索引從 3 開始 (從剛添加完非零元素後面開始)

JAVA 實現

class Solution {
    public void moveZeroes(int[] nums) {

        if (nums == null || nums.length == 0) return; // 防止這個函式會直接回傳傳入的 nums 參數
        int insert = 0;

        // 把非零元素加到當前陣列裡
        for (int num: nums){
            if (num != 0){
                nums[insert++] = num; // 從陣列的最前面開始添加 (注意：元素會先被添加在 nums[insert]裡，之後 insert 才會被 ++)
            }
        }

        // 再把當前的陣列後面補 0 即可，索引從 3 開始
        while (insert < nums.length){
            nums[insert++] = 0; // 添加 0 進去
        }
    }
}

Python 實現

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        
        # 把非零元素加到當前陣列裡
        for i in range(len(nums)):
            if nums[i] !=0: # 不是非 0 元素
                nums[pointer] = nums[i]  # 取得當下元素，放到指定索引裡
                pointer += 1 # 索引++

        # 再把當前的陣列後面補 0 即可，索引從 3 開始
        for i in range(pointer, len(nums)):
            nums[pointer] = 0 # 添加 0 進去
            pointer += 1 # 索引 ++

Python 進階實現

筆者還在學習中，參考了在討論區裡網友討論度很高的 Swap 變數互換簡潔的算法。

把陣列中前面的元素和後面的元素設定好條件 (必須前面為非零元素，後面為零元素)

將兩個元素做交換，把非零元素換到前面

最後後面索引 +1，進行下一次比較交換元素

class Solution:
    def moveZeroes(self, nums: list) -> None:

        slow = 0 

        for fast in range(len(nums)):
            if nums[fast] != 0 and nums[slow] == 0: # 前面的元素、後面的元素
                nums[slow], nums[fast] = nums[fast], nums[slow] # 將兩個元素做交換

            # 第一次循環，剛開始索引 fast[0] slow[0]
            if nums[slow] != 0: 
                slow += 1 # 索引 +1 後，換比較交換 fast[1] ，slow[2]

其他算法

雙指針算法：https://medium.com/@urdreamliu/283-圖解-move-zeroes-4da4900f5aac

成績

Language	Runtime	Memory
Java	1ms	43.9MB
Python	158ms	17.9MB