LeetCode : 905. Sort Array By Parity

[congr]

https://leetcode.com/problems/sort-array-by-parity/

[congr]

two pass, O(N)

class Solution {
    public int[] sortArrayByParity(int[] A) {
        List<Integer> even = new LinkedList();
        List<Integer> odd = new LinkedList();

        for (int n : A) {
            if (n % 2 == 0) even.add(n);
            else odd.add(n);
        }

        for (int i = 0, j = 0; i + j < A.length; ) {
            if (i < even.size())
                A[i] = even.get(i++);
            else A[i+j] = odd.get(j++); 
        }

        return A;
    }
}

[congr]

faster code

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int[] B = new int[A.length];

        for (int i = 0, b = 0, e = A.length-1; i < A.length; i++) {
            if (A[i] % 2 == 0) B[b++] = A[i];
            else B[e--] = A[i];
        }

        return B;
    }
}

[congr]

space : In-place, no additional space time: O(N)

class Solution {
    public int[] sortArrayByParity(int[] A) {
        for (int left = 0, right = 0; right < A.length; right++) {
            if (A[right] % 2 == 0) swap(A, left++, right); // !!!left++
        }

        return A;
    }

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