題目連結: Move Zeroes

題目描述為: 給定一組陣列，我們需要將所有的 0 元素移到陣列最後面，且不更動原本順序。題目有補充說明，希望我們採用 in-place的方式來完成。

例子 1: input=[0,1,0,3,12], output=[1,3,12,0,0]。

思路 1: 創建新陣列

我們可以創建一個新的陣列，大小與原本的一致，依序儲存非 0 元素，最後剩下的位置皆為 0 元素，再將原陣列按照此順序賦值。

• 複雜度評估
  設陣列大小為 N ，我們需要遍歷該陣列兩次，時間複雜度為 O(N)。
  此方法需要創建一個大小為 N 的陣列，空間複雜度為 O(N)。

參考程式碼

func moveZeroes(nums []int)  {
    
    tmp:=make([]int,len(nums))
    idx:=0
              
    for _,v:=range nums{
        
        if v==0{
            continue
        }
                  
        tmp[idx]=v
        idx++   
    }
    
    for i,_:=range nums{
        nums[i]=tmp[i]
    }
    
}

思路 2: 類泡沫排序法

我們可以仿造泡沫排序法的方式，將元素兩兩比較，若前者元素值為 0，則交換位置。

• 複雜度評估
  設陣列大小為 N，泡沫排序法時間複雜度為 O(N²)。
  此方法滿足 in-place，空間複雜度為 O(1)。

參考程式碼

func moveZeroes(nums []int)  {
    
    for i:=0;i<len(nums)-1;i++{
        for j:=i+1;j<len(nums);j++{
            if nums[i]==0{
                nums[i],nums[j]=nums[j],nums[i]
            }
        }
    }
    
}

思路 3: 原地寫入法

我們可以用一個變數 j 初始化為 0，用來紀錄當前寫入的index，直接遍歷整個陣列，當元素不為 0 時，直接擺到 index=j 的位置。當遍歷完後再將 j 當下位置後面的元素皆設為 0。

• 複雜度評估
  設陣列大小為 N，此方法至多需要遍歷該陣列兩次，時間複雜度為 O(N)。
  此方法滿足 in-place，空間複雜度為 O(1)。

參考程式碼

func moveZeroes(nums []int)  {
    
    j:=0 
    for i:=0;i<len(nums);i++{
        if nums[i]!=0{
            nums[j]=nums[i]
            j++
        }        
    }
    
    for j<len(nums){
        nums[j]=0
        j++
    }
}

小結:

方法 1 需要額外的記憶體空間，不滿足 in-place 原則。
方法 2 仿造了泡沫排序法的形式，時間複雜度較高。
方法 3 滿足 in-place 原則，且時間複雜度較低，為此題的理想解法。
我將解法加上簡單的測試，附上程式碼到此。

補充:

當有 N 個元素需要排序時，我們一般認定對它排序的時間複雜度為 O(NlogN)。
而 in-place 原則讓我們注意對記憶體空間的管理。在過去的時代，記憶體空間極少但仍舊完成了登月任務。