905. 按奇偶排序数组
题目描述
输入整数数组 nums。
调整元素顺序，使所有偶数都排在所有奇数前面。
偶数内部、奇数内部的相对顺序不限，返回任意一个满足要求的数组即可。
示例 1
输入：nums = [3,1,2,4] 输出：[4,2,1,3]
解释：偶数 4、2 在前，奇数 1、3 在后；[2,4,3,1] 等也正确。
示例 2
输入：nums = [0] 输出：[0]
数据范围
1 <= nums.length <= 50000 <= nums[i] <= 5000
解题思路
用左右两个指针从两端向中间收缩。i 左边保证都是偶数，j 右边保证都是奇数。每轮先看是否“左奇右偶”，是就交换，一次修正两个放错的数；然后如果 nums[i] 是偶数就把 i 右移，如果 nums[j] 是奇数就把 j 左移。i 与 j 相遇时，整个数组就分好了。
为什么正确
nums[0..i) 全是偶数，nums(j..n-1] 全是奇数；中间 [i, j] 是尚未确定的部分。
复杂度分析
时间 O(n)，每轮 i 右移或 j 左移至少一个；额外空间 O(1)，原地交换。
易错点
循环里三个 if 是并列的，交换后要用交换后的值判断是否移动指针；答案不唯一，只要偶数全在奇数前面就算对。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
i, j = 0, len(nums) - 1
while i < j:
if nums[i] % 2 == 1 and nums[j] % 2 == 0:
nums[i], nums[j] = nums[j], nums[i]
if nums[i] % 2 == 0:
i += 1
if nums[j] % 2 == 1:
j -= 1
return numsclass Solution {
public int[] sortArrayByParity(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 == 1 && nums[j] % 2 == 0) {
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}
if (nums[i] % 2 == 0) {
i++;
}
if (nums[j] % 2 == 1) {
j--;
}
}
return nums;
}
}class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
int i = 0, j = (int)nums.size() - 1;
while (i < j) {
if (nums[i] % 2 == 1 && nums[j] % 2 == 0) {
swap(nums[i], nums[j]);
}
if (nums[i] % 2 == 0) {
i++;
}
if (nums[j] % 2 == 1) {
j--;
}
}
return nums;
}
};func sortArrayByParity(nums []int) []int {
i, j := 0, len(nums)-1
for i < j {
if nums[i]%2 == 1 && nums[j]%2 == 0 {
nums[i], nums[j] = nums[j], nums[i]
}
if nums[i]%2 == 0 {
i++
}
if nums[j]%2 == 1 {
j--
}
}
return nums
}var sortArrayByParity = function(nums) {
let i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 === 1 && nums[j] % 2 === 0) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
if (nums[i] % 2 === 0) {
i++;
}
if (nums[j] % 2 === 1) {
j--;
}
}
return nums;
};function sortArrayByParity(nums: number[]): number[] {
let i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 === 1 && nums[j] % 2 === 0) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
if (nums[i] % 2 === 0) {
i++;
}
if (nums[j] % 2 === 1) {
j--;
}
}
return nums;
}