905. 按奇偶排序数组
905. 按奇偶排序数组
题目
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
解题思路
题目要求按照「偶数在前,奇数在后」的顺序对数组进行排列,可以通过遍历数组并在原地进行交换来实现。
定义变量
- 使用变量
count
记录当前「偶数部分」的分界点索引,即下一个偶数应该被放置的位置。 - 初始化
count
为0
,表示当前还没有处理任何偶数。
- 使用变量
遍历数组
- 遍历数组中的每个元素
nums[i]
:- 如果
nums[i]
是偶数,则将它与nums[count]
进行交换,将偶数移到「偶数部分」的尾部。 - 将分界点
count
向前移动一位。
- 如果
- 如果
nums[i]
是奇数,则不需要任何操作,继续检查下一个元素。
- 遍历数组中的每个元素
返回结果
- 遍历结束后,数组已经按照「偶数在前,奇数在后」的顺序排列,直接返回
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 | 按奇偶性交换后的最大数字 | [✓] | 排序 堆(优先队列) | 🟢 | 🀄️ 🔗 |