0905. Sort Array By Parity - chasel2361/leetcode GitHub Wiki

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.

Example 1: Input: [3,1,2,4] Output: [2,4,3,1] The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. Note: 1 <= A.length <= 5000 0 <= A[i] <= 5000

這個問題要求檢查 list A 中的奇偶整數，將奇數放到後面、偶數放到前面，這個問題可以使用 two pointer 的概念來解決，第一個指標從前往後走，檢查是否為偶數；第二個指標從後往前走，檢查是否為奇數，當兩者皆檢查到預期之外的結果時便將兩者互換，直到兩個指標交錯為止。

寫出來的程式碼長這樣

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        if not A: return []
        i, j = 0, len(A) - 1
        while i < j:
            while A[i] % 2 == 0 and i < j:
                i += 1
            while A[j] %2 == 1 and i < j:
                j -= 1
            if i < j:
                A[i], A[j] = A[j], A[i]
        return A

後來覺得要一直判斷 i<j 好像有點麻煩，所以改用 if 寫

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        if not A: return []
        i, j = 0, len(A) - 1
        while i < j:
            if A[i] % 2 == 0:
                i += 1
                continue
            if A[j] %2 == 1 :
                j -= 1
                continue
            A[i], A[j] = A[j], A[i]
        return A

結果有趣的是，看起來判斷比較少的 if 寫法速度竟然比較慢，可能是 python 執行這兩種判斷式的速度有差別

這兩種寫法的時間複雜度都是 O(N)，空間複雜度為O(1)

---

上面的寫法是 in-place，如果把空間複雜度稍微放寬一點的話速度可以更快

class Solution:
    def sortArrayByParity(self, A: List[int]) -> List[int]:
        B, C = [], []
        for num in A:
            if num % 2 == 0:
                B.append(num)
            else:
                C.append(num)
        return B + C

這個做法又更單純了，而且會按照原本的順序排列，不過時間與空間複雜度都是 O(N)

Code Link