922. 按奇偶排序数组 II

🟢   🔖  数组 双指针 排序  🔗 力扣 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	按奇偶性交换后的最大数字	[✓]	排序 堆（优先队列）	🟢	🀄️ 🔗