给你一个整数数组 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
思路
- 初始化指针:设置两个指针i和j,i从数组左侧开始,j从数组右侧开始。
- 寻找奇数和偶数:使用两个while循环分别寻找数组左侧的第一个奇数(由i指向)和数组右侧的第一个偶数(由j指向)。
- 交换元素:当找到这样的一对奇数和偶数时,交换它们的位置。这样可以确保随着算法的进行,所有偶数逐渐被移到数组的前面,奇数被移到后面。
- 更新指针:交换后,i和j各自向中间移动,i增加,j减少。
- 循环直至重合:当i和j重合或交叉时,循环结束。
- 返回结果:返回修改后的数组A。
时间复杂度:O(n),其中 n 是数组 A 的长度。这是因为每个元素最多被检查一次。 空间复杂度:O(1),因为只使用了两个额外的指针变量,并且排序是原地进行的,不需要额外的存储空间。
/**
* @param {number[]} A
* @return {number[]}
*/
var sortArrayByParity = function (A) {
let i = 0; // 从左向右的指针
let j = A.length - 1; // 从右向左的指针
while (i < j) {
// 找到第一个奇数
while (i < j && A[i] % 2 === 0) {
i++;
}
// 找到第一个偶数
while (i < j && A[j] % 2 !== 0) {
j--;
}
// 交换两个数
if (i < j) {
[A[i], A[j]] = [A[j], A[i]];
i++;
j--;
}
}
return A;
};