0922.md

title	description	keywords
922. 按奇偶排序数组 II	LeetCode 922. 按奇偶排序数组 II题解，Sort Array By Parity II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 922. 按奇偶排序数组 II 按奇偶排序数组 II Sort Array By Parity II 解题思路 数组 双指针 排序

922. 按奇偶排序数组 II

🟢 Easy  🔖  数组 双指针 排序  🔗 力扣 LeetCode

题目

Given an array of integers nums, half of the integers in nums are odd , and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd , and whenever nums[i] is even, i is even.

Return any answer array that satisfies this condition.

Example 1:

Input: nums = [4,2,5,7]

Output: [4,5,2,7]

Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2:

Input: nums = [2,3]

Output: [2,3]

Constraints:

• 2 <= nums.length <= 2 * 10^4
• nums.length is even.
• Half of the integers in nums are even.
• 0 <= nums[i] <= 1000

Follow Up: Could you solve it in-place?

题目大意

给定一个非负整数数组 nums， 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. 双指针初始化

   • even 指针：指向偶数索引（从索引 0 开始），用于检查偶数位置是否存放偶数。
   • odd 指针：指向奇数索引（从索引 1 开始），用于检查奇数位置是否存放奇数。

2. 扫描和交换

   • 遍历数组，同时检查 odd 和 even 指针的值：
     • 如果 nums[odd] 是奇数（满足条件），则 odd 指针后移两个单位，直到 nums[odd] 是偶数（不满足条件）。
     • 如果 nums[even] 是偶数（满足条件），则 even 指针后移两个单位，直到 nums[odd] 是奇数（不满足条件）。
     • 如果 nums[odd] 和 nums[even] 都不符合条件，则交换这两个位置的值，随后各自后移两位。
   • 直到任何一个指针超出数组长度，结束循环。

3. 返回结果

   • 完成调整后返回数组。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，遍历数组一次，查找错误位置并交换。
• 空间复杂度：O(1)，直接在原数组上进行交换，不使用额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParityII = function (nums) {
	const n = nums.length;
	let even = 0; // 初始化双指针
	let odd = 1;

	while (even < n && odd < n) {
		// 找到偶数位置存放奇数的错误
		while (even < n && nums[even] % 2 === 0) {
			even += 2;
		}
		// 找到奇数位置存放偶数的错误
		while (odd < n && nums[odd] % 2 === 1) {
			odd += 2;
		}

		// 如果错误位置均有效，则交换值
		if (even < n && odd < n) {
			let temp = nums[odd];
			nums[odd] = nums[even];
			nums[even] = temp;
		}
	}

	return nums;
};

相关题目

题号	标题	题解	标签	难度	力扣
905	按奇偶排序数组	[✓]	数组 双指针 排序	🟢	🀄️ 🔗
2149	按符号重排数组		数组 双指针 模拟	🟠	🀄️ 🔗
2164	对奇偶下标分别排序	[✓]	数组 排序	🟢	🀄️ 🔗
2231	按奇偶性交换后的最大数字	[✓]	排序 堆（优先队列）	🟢	🀄️ 🔗