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.
class Solution {
public:
/**
* @param A: An integer array.
* @return: void
*/
void rerange(vector<int> &A) {
int n = A.size();
if(n < ) return;
int posNum = , negNum = , posIdx = , negIdx = ;
for(size_t t = ;t < n;++t){
if(A[t] >= ) ++posNum;
else ++negNum;
}
if(negNum > posNum){
negIdx = ;
posIdx = ;
}
while(posIdx < n && negIdx < n){
while(posIdx < n && A[posIdx] >= ) posIdx += ;
while(negIdx < n && A[negIdx] < ) negIdx += ;
if(posIdx < n && negIdx < n) swap(A[posIdx],A[negIdx]);
}
}
};