JZX轻语：简
LeetCode 922 - 按奇偶排序数组 II
发表于2024年05月28日
题目说的是“排序”，实际上不是严格按照递增或递减顺序排，而是说将奇数元素放在奇数位置上，偶数元素放在偶数位置上。朴素的做法就是使用两个数组，分别存放奇数和偶数元素，然后再合并。但是这样的空间复杂度是O(n)，无法就地完成。可以利用双指针的方法，一个指针遍历奇数位置，一个指针遍历偶数位置，然后分别停在不符合要求的位置上，然后交换即可。
class Solution:
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
odd_pos = 1
even_pos = 0
while odd_pos < len(nums) and even_pos < len(nums):
if nums[odd_pos] % 2:
odd_pos += 2
elif not nums[even_pos] % 2:
even_pos += 2
else:
nums[odd_pos], nums[even_pos] = nums[even_pos], nums[odd_pos]
return nums