905. 按奇偶排序数组

在这里插入图片描述

双指针 + 两遍扫描

思路

第一遍，处理偶数
第二遍，处理奇数

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int slow = 0;
        for (int fast = 0; fast < n; fast++) {
            if ((nums[fast] & 1) == 0) {
                res[slow++] = nums[fast];
            }
        }
        for (int fast = 0; fast < n; fast++) {
            if ((nums[fast] & 1) == 1) {
                res[slow++] = nums[fast];
            }
        }
        return res;
    }
}

在这里插入图片描述

时间复杂度： $O (2 n)$
空间复杂度： $O (n)$

双指针 + 一遍扫描 ??

思路 🤔

双指针定义：left 左边都是偶数、right 右边都是奇数
初始化：left = 0、right = n - 1
一遍遍历，如果 nums[left] 为奇数，则不断地和 nums[right] 交换，直到 nusm[left] 为偶数为止

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            while (left <= right && (nums[left] & 1) == 1) {
                // 交换
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                right--;
            }
            // 此时，左端nums[left]一定是偶数
            left++;
        }
        return nums;
    }
}