算法实战-LeetCode之旅

Sort Array By Parity

AC-17ms.
按照《算法导论》排序一章的一些概念，第二种可以称为是原址的（in-place)。
First Try:
用了另一个数组来保存结果，如果是奇数进行swap操作，同时在else中还要维护偶数的位置正确性。

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int[] result = new int[A.length];
        for (int i = 0,tmp = 0; i < A.length; i++) {
            if (A[i] % 2 == 1) {
                result[A.length - tmp - 1] = A[i];
                tmp ++;
            } else {
                result[i - tmp] = A[i];
            }
        }
        return result;
    }
}

提交后瞄了眼，发现可以只操作原数组，改了一下，这次只需要将even数据移到前面即可。

for (int i = 0,evenIndex = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                int tmp = A[i];
                A[i] = A[evenIndex];
                A[evenIndex] = tmp;
                evenIndex ++;
            }
        }
        System.err.println(System.nanoTime() - start + "ms.");
        return A;