前言

嘿嘿～今天我們要來解一道經典的「小而美」題目——Move Zeroes（移動零）！
這題算是 Easy 難度，但不要小看它喔～
能不能寫出乾淨又有效率的解法可是大有學問。題

目要求我們把陣列中的所有 0 都移到最後面，同時保持其他非零元素的相對順序，
而且要原地處理（不能新建陣列喔）。

聽起來有點像在整理房間，把東西移來移去對不對？那我們就來看看這道題怎麼解吧！

英文題目

Move Zeroes

難度：Easy

題目描述：

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.

給定一個整數陣列，將所有的 0 移動到末尾，同時保持非零元素的相對順序。

注意： 必須原地操作，不得複製陣列。

Example 1:

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

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

範例 1：

輸入： nums = [0, 1, 0, 3, 12]

輸出： [1, 3, 12, 0, 0]

範例 2：

輸入： nums = [0]

輸出： [0]

實作

這題目需要注意的是我們要「原地」處理，不能新建陣列，所以我們可以使用雙指針的方法來高效完成這個任務：

function moveZeroes(nums: number[]): void {
    let lastNonZeroFoundAt = 0; // 用來標記下一個非零元素應放的位置

    // 第一遍循環：把所有非零元素按順序移動到陣列前面
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            nums[lastNonZeroFoundAt] = nums[i];
            lastNonZeroFoundAt++;
        }
    }

    // 第二遍循環：把剩餘位置填上 0
    for (let i = lastNonZeroFoundAt; i < nums.length; i++) {
        nums[i] = 0;
    }
}

解題心法

1. 使用雙指針法：標記非零元素的位置

   我們用一個指針 lastNonZeroFoundAt 來追蹤目前非零元素應該放的位置，初始值設為 0，代表陣列的開頭。

2. 第一遍循環：把非零元素移動到陣列前面

   • 從左到右遍歷陣列，遇到非零元素時，就將它放到 lastNonZeroFoundAt 指針位置，然後指針右移一格。
   • 這樣做的好處是，我們可以保證所有的非零元素依次放在陣列的前端，同時保持它們的相對順序。

3. 第二遍循環：將後面的元素全部設為 0

   • 完成非零元素的移動後，lastNonZeroFoundAt 指針的位置就是第一個應該填 0 的位置。
   • 從這個位置開始，把剩餘的所有元素都設為 0，這樣我們就完成了題目的要求。

為什麼這樣處理？

這種處理方式的核心在於我們不需要新建陣列，而是原地進行所有的操作，最大化效率。
雙指針法的好處是可以輕鬆管理非零元素的位置，並確保順序不變，同時避免不必要的元素交換，將時間複雜度控制在 O(n)，而且代碼簡潔易懂。

本次要點：

• 使用雙指針法，高效地將非零元素移到陣列前端。
• 保持非零元素的相對順序，確保不影響數據的正確性。
• 最後將陣列後面的元素全部填為 0，達成題目要求。

這樣解完這題，是不是覺得整理陣列也變得輕鬆有趣了呢？
解題過程中，只要牢記這些心法，就能輕鬆搞定各種排列問題喔！
期待下次再和大家一起解題～٩(๑❛ᴗ❛๑)۶