leetcode （Sort Array By Parity）

Title：Sort Array By Parity    905

Difficulty：Easy

原题leetcode地址：https://leetcode.com/problems/sort-array-by-parity/

 

1.  双指针

时间复杂度：O(n)，一次一层while循环，需要遍历整个数组。

空间复杂度：O(1)，没有申请额外的空间。

    /**
     * 采用双指针，将前面奇数与后面的偶数互换，直到互换为止
     * @param A
     * @return
     */
    public static int[] sortArrayByParity(int[] A) {

        int beginIndex = 0;
        int endIndex = A.length - 1;

        while (beginIndex < endIndex) {
            if (A[beginIndex] % 2 == 1 && A[endIndex] % 2 == 0) {
                int tmp = A[beginIndex];
                A[beginIndex] = A[endIndex];
                A[endIndex] = tmp;
                beginIndex++;
                endIndex--;
            }
            else if (A[beginIndex] % 2 == 0 && A[endIndex] % 2 == 0) {
                beginIndex++;
            }
            else if (A[beginIndex] % 2 == 1 && A[endIndex] % 2 == 1) {
                endIndex--;
            }
            else if (A[beginIndex] % 2 == 0 && A[endIndex] % 2 == 1) {
                beginIndex++;
                endIndex--;
            }
        }

        return A;

    }