905. 按奇偶排序数组

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

题目

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Example 1:

Input: nums = [3,1,2,4]

Output: [2,4,3,1]

Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0]

Output: [0]

Constraints:

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

题目大意

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1：

输入： nums = [3,1,2,4]

输出：[2,4,3,1]

解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例 2：

输入： nums = [0]

输出：[0]

提示：

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

解题思路

题目要求按照「偶数在前，奇数在后」的顺序对数组进行排列，可以通过遍历数组并在原地进行交换来实现。

1. 定义变量

   • 使用变量 count 记录当前「偶数部分」的分界点索引，即下一个偶数应该被放置的位置。
   • 初始化 count 为 0，表示当前还没有处理任何偶数。

2. 遍历数组

   • 遍历数组中的每个元素 nums[i]：
     1. 如果 nums[i] 是偶数，则将它与 nums[count] 进行交换，将偶数移到「偶数部分」的尾部。
     2. 将分界点 count 向前移动一位。
   • 如果 nums[i] 是奇数，则不需要任何操作，继续检查下一个元素。

3. 返回结果

   • 遍历结束后，数组已经按照「偶数在前，奇数在后」的顺序排列，直接返回 nums。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，遍历数组一次，每次交换元素的操作是常数时间
• 空间复杂度：O(1)，使用了常数个变量。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParity = function (nums) {
	let count = 0; // 记录下一个偶数应该放置的位置
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] % 2 === 0) {
			// 如果是偶数
			// 交换 nums[i] 和 nums[count]
			let temp = nums[count];
			nums[count] = nums[i];
			nums[i] = temp;
			count++; // 偶数部分的边界右移
		}
	}
	return nums; // 返回排列后的数组
};

相关题目

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