前言

　　這題題目要設法將陣列中的非零元素全部往前移，題目要求不能配置新的空間，所以不能使用輔助的 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?

範例

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

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

成績

(新手上路，如有錯誤請友善告知，感謝)

Blog
https://chris81051.github.io/2023/05/05/LeetCode-283-Move-Zeroes-Java-Python/
有分享技術文章、科技新聞、日常生活，歡迎一起討論