#283. Move Zeroes

題目描述

給你一個整數陣列nums，整理非0值的數字排序，將所有的0移動到陣列的後面。

你只能在同一個陣列中操作，不能使用複製陣列來完成。

限制條件

1. 1 <= nums.length <= 104
2. -231 <= nums[i] <= 231 - 1
3. 只能在同一個陣列中操作，不能使用額外的空間完成任務。

解題思路

由於不能使用複製陣列的方式來整理數字，所以能夠解決的選項就很少了。

Two Pointers

這題可以使用雙指標來解決，第一個指標用來定位0值，另外一個指標用來往後搜尋需要往前放的非0值。 當兩個指標任一達到尾端時，就算陣列整理完成了。

public class Solution { 
	public int[] Solver(int[] nums){ 
		int zPos = 0;		
        while(zPos<nums.Length-1){
            while(nums[zPos]!=0){
              zPos++;
              if(zPos>=nums.Length-1) return;
            }
            for(int i=zPos+1;i<nums.Length;i++){
                if(nums[i]!=0){
                    nums[zPos] = nums[i];
                    nums[i] = 0;
                    break;
                }
                if(i==nums.Length-1) return;
            }
        }
	}
}

複雜度分析：

• 時間複雜度：最差的情況會是兩個指標都要跑一次全部的陣列，像是[0 ... 0 ... 1]這種狀況，總時間為2N，因此時間複雜度為O(N)。
• 空間複雜度：由於是in-place操作，因此空間複雜度為O(1)。

Follow-up

你可以減少執行的次數嗎？

Two Pointers Improvement

上一個解決方式最差會產生讓兩個指標都要走完一次陣列的情況，我們可以稍微調整一下順序，由尋找非0值的指標為基準，首先先定位最近的0值位置，然後開始往後找非0值，這個時候找到的非0值如果位置比0值小，代表它位於整理好的位置，如果比0值大，代表它需要被往前移動到0值的位置。

以這個順序來執行的話，0值指標最多只會走到已經整理過的非0值的末端位置，而非0值指標會走完全部的陣列，因此執行的次數會略低於上一個解決方法。

public class Solution { 
	public int[] Solver(int[] nums){ 
		int zPos = 0;
        for(int i=0;i<nums.Length;i++){
            while(nums[zPos]!=0){
              zPos++;
              if(zPos==nums.Length) return;
            }                         
            if(nums[i]!=0 && i>zPos){
              nums[zPos] = nums[i];
              nums[i] = 0;
            }
        }
	}
}

複雜度分析：

• 時間複雜度：非0值指標一定會跑完全部的陣列，0值指標最多只會到達非0值數字的末端，總執行時間為(N< n <2N)，因此時間複雜度為O(N)。
• 空間複雜度：由於是in-place操作，因此空間複雜度為O(1)。

學習重點

• 雙指標