一魚多吃 用雙指針的觀念來解 Move Zeroes 搬移零 Leetcode #283

這題的題目在這裡

題目會給定我們一個陣列，要求我們重新安排順序，把等於零的數字搬到後面。同時必須保持原本數字的前後相對次序。

比如說，移動之前，1 在 3前面，那麼移動之後，1還是必須保持在3前面。

(接著看下面的範例，會更好理解)

測試範例:

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
保持原本數字的前後相對次序

Example 2:

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

約束條件:

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Follow up: Could you minimize the total number of operations done?

演算法:

其實和前面那題  Sort Array By Parity 九成像，前面那題是要求偶數的排在前面，奇數的排在後面。

這題換湯不換藥，稍微小小改一下，題目要求 等於零的排在後面，
等價於 把不等於0的排在前面。

一般寫loop習慣大多是從左到右掃描，所以這題從 不等於0 切入，就會簡單很多。

把不等於0的排在前面，當我們搬完之後，等於0的也會剛好排在後面。

註: 因為是位置交換，不等於0的往前挪了，一定會有一個等於0的往後挪。

程式碼:

class Solution:
　def moveZeroes(self, nums: List[int]) -> None:
　　
　　# swapping index for nonzero numbers
　　idx_of_nonzero = 0

　　is_nonzero = lambda x: x != 0

　　# scan each element
　　for i in range(len(nums)):
　　　
　　　if is_nonzero(nums[i]):

　　　　# swap non-zero number to the left-hand side
　　　　nums[ idx_of_nonzero ], nums[i] = nums[i], nums[ idx_of_nonzero ]
　　　　idx_of_nonzero += 1
　　　　
　　return nums

時間複雜度:

O( n ) 一個單層的 for loop 迭代，掃描過每個數字一次。

空間複雜度:

O(1) 只用到固定一組雙指針double pointer，所占用的記憶體空間為常數級別O(1)

另解:

class Solution:
　def moveZeroes(self, nums: List[int]) -> None:

　　zeroCount = 0

　　for i in range( len(nums) ):

　　　# 統計0的出現次數
　　　if nums[i] == 0:
　　　　zeroCount += 1
　　　
　　　# 把 非0的數字搬到前面，並且保持原本的前後次序​
　　　elif zeroCount > 0:
　　　　nums[i-zeroCount], nums[i] = nums[i], nums[i-zeroCount]

　　return 

時間複雜度:

O( n ) 一個單層的 for loop 迭代，掃描過每個數字一次。

空間複雜度:

O(1) 只用到固定的臨時變數 和 計數器，所占用的記憶體空間為常數級別O(1)

學完這題之後，記得回去複習原本的那一題 Sort Array by Parity，背後的核心觀念，都是數字先分類成兩群(奇數 偶數、等於零 不等於零)，再做移動的操作。

Reference:

[1] Python O(n) by element swap [w/ Comment] - Move Zeroes - LeetCode