陣列操作入門題 Sort Array By Parity Leetcode #905

這題的題目在這裡

題目會給定一個陣列，要求我們把裡面的數字依照奇偶數去排序，
偶數的排在前面，奇數的排在後面。

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
偶數排在前面，奇數排在後面。​

Example 2:

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

約束條件:

Constraints:

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

演算法:

雖然題目名字提到了排序sort，但是我們不需要真的去使用O(n log n)的排序演算法。

為什麼?

因為題目要求的條件其實比較寬鬆，並沒有要求比大小，只需要奇偶數區分開來即可。

那麼我們可以使用雙指針的技巧，一個指針負責掃描所有元素，另一個指針負責把偶數swap到相對前面的位置(相較之下，在swap之後，奇數自然就落在後面的位置)。

程式碼:

class Solution:
　def sortArrayByParity(self, A: List[int]) -> List[int]:
　　
　　idx_of_even = 0
　　
　　is_even_number = lambda x: not( x & 1 )
　　
　　for i in range(len(A)):
　　　# scan each element
　　　
　　　if is_even_number(A[i]):
　　　
　　　　# swap even number to the left-hand side
　　　　
　　　　A[idx_of_even], A[i] = A[i], A[idx_of_even]
　　　　idx_of_even += 1
　　　　
　　return A

時間複雜度:

O( n ) 每個元素掃描一遍即可。

空間複雜度:

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

其實這題的swap概念，和quick sort 內部在做分割 partition的那個模組很像，讀者空閒之餘可以細細體會，其實觀念是相通的。

Reference:

[1] Python O(n) by two-pointers [w/ Visualization] - Sort Array By Parity - LeetCode