Interleaving Positive and Negative Numbers

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

Note

You are not necessary to keep the original order or positive integers or 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 legal answer.
 

 
class Solution {
public:
   void swap(vector &A, int i, int j) {
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
   }
   
    /**
     * @param A: An integer array.
     * @return an integer array
     */
    vector rerange(vector &A) {
        int n = A.size();
        
        // by default, start with negative in output array
        int expectPostive = false;
        int postiveCount = 0;
        for(int k : A) 
            postiveCount += k > 0? 1 : 0; 
            
        // if there are more postive than negative, start with postive
        if (2*postiveCount > n)
           expectPostive = true;
        
        int i = 0, j = 0;
        int idx = 0;        
        
        while(i < n && j < n) {
           // A[i] is the next negative
           while( i < n && A[i] > 0) i++;
           // A[j] is the next postive
           while( j < n && A[j] < 0)  j++;
           
           if (expectPostive && A[idx] < 0) 
                   swap(A, idx, j); 
           
           if (!expectPostive && A[idx] > 0)
               swap(A, idx, i);
           
           if (idx == i) i++;
           if (idx == j) j++;
           expectPostive = !expectPostive;
           idx++;
        }
        
        return A;
    }
};