按奇偶排序数组
给你一个整数数组nums，将nums中的的所有偶数元素移动到数组的前面，后跟所有奇数元素
返回满足此条件的任一数组作为答案
示例 ：
输入： nums = [3,1,2,4]
输出： [2,4,3,1]
解释： [4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。
提示：
- 1 <= nums.length <= 5000
- 0 <= nums[i] <= 5000
思路一：暴力求解
-
新建一个数组用来保存排序完毕的数组
-
第一次遍历时把所有偶数依次追加到新数组中
-
第二次遍历时把所有奇数依次追加到新数组中
class Solution {
public int[] sortArrayByParity(int[] nums) {
int [] arr=new int[nums.length];
int count=0;
for(int i=0;i<nums.length;i++){
if(nums[i]%2==0){
arr[count]=nums[i];
count++;
}
}
for(int i=0;i<nums.length;i++){
if(nums[i]%2!=0){
arr[count]=nums[i];
count++;
}
}
return arr;
}
}
思路二：双指针 + 一次遍历
-
记数组nums 的长度为 n
-
新建一个长度为 n的数组res 用来保存排完序的数组
-
遍历一遍nums，遇到偶数则从res 左侧开始替换元素
-
遇到奇数则从res 右侧开始替换元素
-
遍历完成后，res 就保存了排序完毕的数组。
class Solution {
public int[] sortArrayByParity(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int left = 0, right = n - 1;
for (int num : nums) {
if (num % 2 == 0) {
res[left++] = num;
} else {
res[right--] = num;
}
}
return res;
}
}
思路三：原地交换
- 记数组nums 的长度为 n
- 先从nums 左侧开始遍历，如果遇到的是偶数，就表示这个元素已经排好序了，继续从左往右遍历，直到遇到一个奇数
- 然后从nums 右侧开始遍历，如果遇到的是奇数，就表示这个元素已经排好序了，继续从右往左遍历，直到遇到一个偶数
- 交换这个奇数和偶数的位置，并且重复两边的遍历，直到在中间相遇，nums 排序完毕。
class Solution {
public int[] sortArrayByParity(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
while (left < right && nums[left] % 2 == 0) {
left++;
}
while (left < right && nums[right] % 2 == 1) {
right--;
}
if (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
return nums;
}
}
