Interleaving Positive and Negative Numbers

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

Have you met this question in a real interview? 

Yes

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.

class Solution {

    /**

     * @param A: An integer array.

     * @return: void

     */

    public void rerange(int[] A) {

        // write your code here

        int n = A.length;

        int posCnt = 0;

        

        for(int num : A){

            posCnt += num > 0 ? 1 : 0;

        }

        boolean expectPositive = posCnt * 2 > n ? true : false;

        int i = 0, j = 0, idx = 0;

        

        while(idx < n){

            

            while(i < n && A[i] < 0) i++;

            while(j < n && A[j] > 0) j++;

            

            if(expectPositive && A[idx] < 0)

                swap(idx, i, A);

            if(!expectPositive && A[idx] > 0)

                swap(idx, j, A); 

            if(idx == i) i++;

            if(idx == j) j++;

            

            expectPositive = !expectPositive;

            idx++;

            

        }

   }

   

   private void swap(int i, int j, int[] A){

       int temp = A[i];

       A[i] = A[j];

       A[j] = temp;

   }

}