LeetCode 解題練習：Sort Array By Parity

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/sort-array-by-parity/

中文描述

給定一個整數陣列 nums ，產生一個陣列將nums中所有偶數放在陣列開頭，放完偶數後再放奇數。

範例一：

輸入 nums = [5, 2, 4, 1] 

輸出 [2, 4, 5, 1] 或 [4, 2, 1, 5] 或 [2, 4, 1, 5] 或 [4, 2, 5, 1] 皆可為答案

範例二：

輸入 nums = [5, 2, 1] 

輸出 [2, 5, 1] 或 [2, 1, 5] 皆可為答案

解法一：

建立一個陣列 parityArr ，迴圈走訪 nums 陣列，若 nums[i] 為偶數，加到 parityArr 最前面；若 nums[i] 為奇數，加到 parityArr 最後面。

Python Code

class Solution:

    def sortArrayByParity(self, nums: List[int]) -> List[int]:

        parityArr = []

       

        for n in nums:

            if n % 2 == 0:

                parityArr.insert(0, n) # 偶數加到parityArr最前面

            else:

                parityArr.append(n) # 奇數加到parityArr最後面

        return parityArr

解法二：

同解法一，但用 Python List Comprehension 語法。

Python Code

class Solution:

    def sortArrayByParity(self, nums: List[int]) -> List[int]:

        parityArr = [n for n in nums if n % 2 == 0] + [n for n in nums if n % 2 == 1]

       

        return parityArr

解法三：

雙指標。當 even 小於 odd時，even 從左開始找非偶數的位置， odd 從右邊開始找非奇數位置，將 nums[even] 與 nums[odd] 互換。參考底下圖片說明

Python Code

class Solution:

    def sortArrayByParity(self, nums: List[int]) -> List[int]:

        even = 0

        odd = len(nums) - 1

       

        while even < odd:

            while even < odd and nums[even] % 2 == 0: even += 1

            while even < odd and nums[odd] % 2 == 1: odd -= 1

            nums[even], nums[odd] = nums[odd], nums[even]

       

        return nums