解决 LeetCode 922 题：按奇偶排序数组 II

题目描述

给定一个非负整数数组 nums，其中一半整数是奇数，一半整数是偶数。要求对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时，i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例

示例 1

输入：

nums = [4, 2, 5, 7]

输出：

[4, 5, 2, 7]

解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

示例 2

输入：

nums = [2, 3]

输出：

[2, 3]

提示

2 <= nums.length <= 2 * 10^4
nums.length 是偶数
nums 中一半是偶数
0 <= nums[i] <= 1000

思路分析

1. 基本思路

给定一个数组 nums，题目要求将数组中的偶数放在所有偶数索引位置（即偶数下标），将奇数放在所有奇数索引位置。由于题目给定了一个条件：数组中一半是奇数，一半是偶数，因此，我们只需要将所有偶数和奇数分开并分别放置到合适的索引位置。

2. 如何分配偶数和奇数？

遍历整个数组，找出其中的偶数和奇数。
使用两个数组 even 和 odd 分别存放偶数和奇数。
然后将 even 中的偶数按照偶数索引（0, 2, 4, …）放入结果数组，将 odd 中的奇数按照奇数索引（1, 3, 5, …）放入结果数组。

3. 时间复杂度

遍历数组的时间复杂度为 O(n)，其中 n 是数组的长度。
每次操作都只需要常数时间，因此总的时间复杂度为 O(n)。

4. 空间复杂度

我们使用了两个额外的数组 even 和 odd，所以空间复杂度是 O(n)。

代码实现

class Solution:def sortArrayByParityII(self, nums: List[int]) -> List[int]:n = len(nums)even = []  # 存储偶数odd = []   # 存储奇数res = []   # 最终结果数组# 将偶数和奇数分开for num in nums:if num % 2 == 0:even.append(num)else:odd.append(num)# 将偶数和奇数分别放到合适的位置for i in range(n // 2):res.append(even[i])  # 偶数放在偶数位置res.append(odd[i])   # 奇数放在奇数位置return res

代码解释

初始化：
- n = len(nums) 获取数组的长度。
- even 和 odd 数组分别用于存储偶数和奇数。
- res 数组用于存放最终的结果。
遍历数组：
- 使用 for num in nums 遍历数组中的每个元素。
- 判断当前元素是偶数还是奇数，将偶数放入 even 数组，将奇数放入 odd 数组。
填充结果数组：
- 使用 for i in range(n // 2) 遍历每个偶数位置。
- 在每个偶数位置放入 even[i]，在每个奇数位置放入 odd[i]。
返回结果：
- 最终返回 res 数组，即按奇偶排序后的数组。

优化建议

进阶：在原地操作，减少空间使用

题目要求我们使用更少的额外空间。可以使用原地交换的方法来解决问题，不需要额外创建新的数组。

优化思路：

我们可以直接在原数组 nums 中进行交换。
使用两个指针 even_index 和 odd_index，分别指向数组中的偶数位置和奇数位置。
如果当前 even_index 位置不是偶数，就与下一个偶数交换；如果当前 odd_index 位置不是奇数，就与下一个奇数交换。

代码实现（原地交换）

class Solution:def sortArrayByParityII(self, nums: List[int]) -> List[int]:even_index = 0  # 偶数位置odd_index = 1   # 奇数位置while even_index < len(nums) and odd_index < len(nums):if nums[even_index] % 2 == 0:even_index += 2  # 如果当前偶数位置是偶数，直接跳到下一个偶数位置elif nums[odd_index] % 2 != 0:odd_index += 2  # 如果当前奇数位置是奇数，直接跳到下一个奇数位置else:# 如果当前偶数位置是奇数，当前奇数位置是偶数，交换它们nums[even_index], nums[odd_index] = nums[odd_index], nums[even_index]even_index += 2odd_index += 2return nums

代码解析

偶数和奇数指针：
- even_index = 0，odd_index = 1，分别指向数组中的偶数和奇数位置。
遍历交换：
- 当 even_index 指向偶数，odd_index 指向奇数时，如果它们不满足条件（偶数位置不是偶数，奇数位置不是奇数），就交换它们。
返回结果：
- 返回修改后的 nums 数组，直接在原数组上进行操作。