LeetCode 922. 按奇偶排序數組 II | Python

922. 按奇偶排序數組 II

題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/sort-array-by-parity-ii/

題目

給定一個非負整數數組

A

， A 中一半整數是奇數，一半整數是偶數。

對數組進行排序，以便當

A[i]

為奇數時，

i

也是奇數；當

A[i]

為偶數時，

i

也是偶數。

你可以傳回任何滿足上述條件的數組作為答案。

示例：

輸入：[4,2,5,7]
輸出：[4,5,2,7]
解釋：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也會被接受。
           

提示：

1. 2 <= A.length <= 20000

2. A.length % 2 == 0

3. 0 <= A[i] <= 1000

解題思路

思路：兩次周遊，一次周遊（雙指針）

先審題，首先題目中說明，給定的非負整數數組中，一半是偶數，一半是奇數。

題目要求對數組進行排序，其中若

A[i]

為奇數時，

i

也應該是奇數；若

A[i]

為偶數時，

i

也應該是偶數。

兩次周遊

在這裡，我們可以使用兩次周遊的思路。

因為數組中，一半是偶數，一半是奇數。那麼我們第一次周遊的時候，先将元素為偶數的，先放到對應索引為偶數的位置上。

第二次周遊的時候，将元素為奇數的放到對應索引為奇數的位置上。

具體的代碼實作如下。

class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        n = len(A)

        ans = [0] * n
        # 第一次周遊
        # 将偶數放到索引為偶數的位置上
        x = 0
        for i in range(n):
            if A[i] % 2 == 0:
                ans[x] = A[i]
                x += 2
        # 第二次周遊
        # 将奇數放到索引為奇數的位置上
        y = 1
        for j in range(n):
            if A[j] % 2 == 1:
                ans[y] = A[j]
                y += 2
        
        return ans
           

一次周遊（雙指針）

上面的方法中，通過兩次周遊的方法，先将元素為偶數放置到索引為偶數的位置上，然後将元素為奇數的放置在索引為奇數的位置上，最終傳回。

但其實我們可以使用一次周遊的形式來完成，這裡需要借助雙指針。具體的做法如下：

• 首先定義雙指針

  i

  、

  j

  ，

  i

  指向索引為 的位置，

  j

  指向索引為

  1

  的位置。
• 周遊數組，如果

  A[i]

  是奇數時，那麼移動

  j

  （移動步長為 2）找到偶數與

  A[i]

  進行數值交換；
• 交換完成後，移動

  i

  （步長為 2），循環步驟 2；
• 當數組周遊結束後，最終所有的數都會放到相應的位置。

具體的代碼實作如下。

class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        i = 0
        j = 1

        n = len(A)
        while i < n:
            # 因為 i 從 0 開始，步長為 2，均為偶數索引
            # 先判斷 A[i] 是否為奇數，為奇數需要交換
            if A[i] % 2 == 1:
                # j 從 1 開始，步長為 2，均為奇數索引
                # 移動 j，找到偶數進行交換
                while A[j] % 2 != 0:
                    j += 2
                A[i], A[j] = A[j], A[i]
            # 步長為 2
            i += 2
        
        return A
           

歡迎關注

公衆号 【書所集錄】

如有錯誤，煩請指出，歡迎指點交流。