Given an arrayAof non-negative integers, return an array consisting of all the even elements ofA, followed by all the odd elements ofA.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

这道题是3 way partition的一个变种

3 way partition: https://algs4.cs.princeton.edu/lectures/23DemoPartitioning.pdf

这道题里只需要把交换的条件改成能不能被2整除就可以了

class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A == null || A.length <= 1)
            return A;

        int left = 0;
        int i = 0; 
        int right = A.length - 1;

        while(i <= right) {
            if(A[i] % 2 == 0)
                swap(A, left++, i++);
            else
                swap(A, i, right--);
        }

        return A;
    }

    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}