Interleaving Positive and Negative Numbers

Problem

Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.

Example

Given [-1, -2, -3, 4, 5, 6], after re-range, it will be [-1, 5, -2, 4, -3, 6] or any other reasonable answer.

Note

You are not necessary to keep the original order of positive integers or negative integers.

Challenge

Do it in-place and without extra memory.

Code - Java

class Solution {
    /**
     * @param A: An integer array.
     * @return: void
     */
    public void rerange(int[] A) {
        int cntPos = 0;
        for (int i : A) {
            if (i > 0) cntPos++;
        }

        if (cntPos > A.length - cntPos) {
            // even: pos, odd: neg
            int i = 0, j = 1;
            while (i < A.length && j < A.length) {
                while (A[i] > 0 && i + 2 < A.length) i += 2;
                while (A[j] < 0 && j + 2 < A.length) j += 2;
                if (A[i] < 0 && A[j] > 0) {
                    int tmp = A[i];
                    A[i] = A[j];
                    A[j] = tmp;
                }
                i += 2;
                j += 2;
            }
        } else {
            // even: neg, odd: pos
            int i = 0, j = 1;
            while (i < A.length && j < A.length) {
                while (A[i] < 0 && i + 2 < A.length) i += 2;
                while (A[j] > 0 && j + 2 < A.length) j += 2;
                if (A[i] > 0 && A[j] < 0) {
                    int tmp = A[i];
                    A[i] = A[j];
                    A[j] = tmp;
                }
                i += 2;
                j += 2;
            }
        }
    }
}