Q: Interleaving Positive and Negative Numbers

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

Notice

You are not necessary to keep the original order of 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 reasonable answer.

Note:

1. 先計算正負數量的多寡
2. 透過跳躍方式交換

    public void rerange(int[] A) {
        //sort + swap : O(nlogn)
        //check + swap : O(n) since we don't care about the order

        //corner case
        if (A == null || A.length == 0) {
            return;
        }

        int posNum = 0, negNum = 0;  
         for (int i = 0; i < A.length; i++) {  
             if (A[i] > 0) {  
                 posNum++;  
             } else {  
                 negNum++;  
             }  
         }  
         int posInd = 1, negInd = 0;  
         if (posNum > negNum) {  
             posInd = 0;  
 //從0開始
             negInd = 1;  
 //從1開始
         }  

         while (negInd < A.length && posInd < A.length) {  
             while (negInd < A.length && A[negInd] < 0) {  
                 negInd += 2;  
             }  
             while (posInd < A.length && A[posInd] > 0) {  
                 posInd += 2;  
             }  
             if (posInd < A.length && negInd < A.length) {  
                 swap(A, posInd, negInd);  
                 posInd += 2;  
                 negInd += 2;  
             }  
         }  
   }

   private void swap(int[] nums, int i, int j){
       if(i == j){ return ;}
       int temp = nums[i];
       nums[i] = nums[j];
       nums[j] = temp;
   }