描述

思路1：双指针+交换

参考快排思想，i从前往后，j从后往前，找到不符合条件的值，进行交换

public class Solution {
    public int[] reOrderArrayTwo (int[] array) {
        int i = 0;
        int j = array.length - 1;
        while(i < j) {
            //i从前往后，找到第一个偶数
            while(i < j && array[i] % 2 == 1) {
                i++;
            }
            //j从后往前，找到第一个奇数
            while(i < j && array[j] % 2 == 0) {
                j--;
            }
            if(i < j) {
                swap(array, i, j);
            }
        }
        return array;
    }
    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

思路2：快慢指针

参考快排思想。奇数在前，偶数在后，index记录下一个奇数填入的位置

public class Solution {
    public int[] reOrderArrayTwo (int[] array) {
        int index = 0;
        for(int i = 0; i < array.length; i++) {
            if(array[i] % 2 == 1) {
                swap(array, i, index);
                index++;
            }
        }
        return array;
    }
    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

思路3：复制

1. 遍历统计奇数个数
2. 再次遍历将奇数填入新数组前半部分，将偶数填入后半部分。使用x和y记录下一个奇数和偶数的填充位置

public class Solution {
    public int[] reOrderArrayTwo (int[] array) {
        int count = 0;
        int[] ret = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            if(array[i] % 2 == 1) {
                count++;
            }
        }
        int x = 0;
        int y = count;
        for(int i = 0; i < array.length; i++) {
            if(array[i] % 2 == 1) {
                ret[x] = array[i];
                x++;
            } else {
                ret[y] = array[i];
                y++;
            }
        }
        return ret;
    }
}