目標：
這題主要目的在於讓讀者繼續熟悉一些陣列的常用操作及方法。

原題：

Question:
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

分析/解題：
題目給定一個陣列nums並要求將所有當中的0全部都放到最後面，
且必須保持所有非0的元素的原有相對排列。
另外Note中還要求必須要in-place且最小化總共操作的次數。

這題其實有很多變形，雖然簡單，
務必請留意題目所要求的條件，不要倉促作答。

首先題目強調必須in-place(in-place的部分先前的文章有提到過)，
故諸如開一個ArrayList/List來將所有非0的部分一個一個存起來的方法，
在這裡就完全行不通了。

直覺上或許讀者會想到諸如以下的方法：

1. 從頭開始找到第一個0元素(位置假設為a)
2. 找到從這個0元素以後第一個非0的元素
3. 將兩者交換
4. 從a+1開始找到下一個0元素
5. 再找到從這個0元素以後第一個非0的元素
6. 按照這樣的邏輯直到沒有更多的0元素，或找到0元素以後，
   其後沒有非0的元素為止。
   (上面的方法沒有很嚴謹，因為1有可能就已經找不到0元素了，
   僅為大概的範例)

但這樣的方法對每一個0元素都有可能需要掃瞄過一整個陣列，
總體的時間複雜度會來到O(N^2)。

有更好的方法嗎？
我們可以先考慮：
如果我們將原先的陣列當成額外開的ArrayList或List來使用的話呢？
先將所有的非0值從index 0開始放入，直到沒有非0的元素為止，
接著，和開新的空間不同，後面多出來的部分相當於被排開的0，
所以我們要將後面的值全部設為0。

這麼做只需要記錄當前非0的部分放到哪邊，在其後再進行補0的動作即可，
最極端的狀況是全部都是0(即完全不用更動陣列)，
以及全部都非0(即將原本的位置複寫相同的數字一次)；
一旦中間有出現0的狀況，只代表其後的數字被往前挪一格，
讀者可以紙筆稍加操作看看即可確認不會有非0的數字會被吃掉XD~

我們使用了index來記錄下一個即將被寫入非0數字的位置，
遍歷整個陣列/串列，當元素非0時，則將其寫入index的位置，
並遞增index，其程式碼如下所示。

Java:

class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) nums[index++] = nums[i];
        }
        while (index < nums.length) {
            nums[index++] = 0;
        }
    }
}

Python:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        index = 0
        for i in range(len(nums)):
            if nums[i]:
                nums[index] = nums[i]
                index += 1
        for j in range(index, len(nums)):
            nums[j] = 0

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(O(N), O(1)，因為最多只須掃過陣列兩次即可)

「如果不要求順序保持相同的話呢？」
(使用two pointer的方式，i由頭至尾，j由尾至頭，
分別找到0和非0的元素進行交換，直到彼此交會即可。
時間/空間複雜度相同但可預期因只須掃過一次陣列，有機會較快)

「如果不要求要in-place呢？」
(以python為例:
res=[x for x in nums if x != 0]
res += (len(nums)- len(res)) * [0]
(後面再接上對應個數的0即可)
(時間/空間複雜度O(N),O(N))

所以，有些題目簡單歸簡單，看到的時候，還是請留心限制條件，
它有可能跟你熟悉的題目有些出入！有時候一旦限制條件不同，
可以用的手段和時間/空間複雜度可能就會完全不同了！

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0096. Unique Binary Search Trees (Medium)