题目：按奇偶排序数组 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] 也会被接受。

提示：

• 2 <= A.length <= 20000
• A.length % 2 == 0
• 0 <= A[i] <= 1000

来源：力扣（LeetCode）第922题

链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii

分析：

一遍遍历数组即可求解。但是为了追求极致，采用双指针法可以实现原地交换。

思路：

• 使用两个指针i,j。
• 一个遍历偶数下标，一个遍历奇数下标。
• 如果i在偶数的下标中找到了一个奇数，那么就从j奇数下标中找一个偶数。
• 将两者交换位置。

代码：

• 双指针法：

  class Solution:
  def sortArrayByParityII(self, A: List[int]) -> List[int]:
      j = 1
      for i in range(0, len(A), 2):
          if A[i] % 2 == 1:
              while A[j] % 2 == 1:
                  j += 2
              A[i], A[j] = A[j], A[i]
      return A
  

• 正常一次遍历：

  class Solution:
  def sortArrayByParityII(self, A: List[int]) -> List[int]:
      ans = [0 for _ in range(len(A))]
      single = 1
      double = 0
      for i in range(len(A)):
          if A[i] % 2 == 0:
              ans[double] = A[i]
              double += 2
          else:
              ans[single] = A[i]
              single += 2
      return ans
  

复杂度分析：

• 双指针法：
  • 时间复杂度：O(n) n 为数组长度
  • 空间复杂度：O(1)
• 正常遍历：
  • 时间复杂度：O(n) n 为数组长度
  • 空间复杂度：O(n)

总结：

• 双指针法可以降低空间的使用，用过原地交换实现不需要额外的空间去储存答案。