題目會給定一個陣列,要求我們把裡面的數字依照奇偶數去排序,
偶數的排在前面,奇數的排在後面。
測試範例:
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