Lintcode 144. Interleaving Positive and Negative Numbers

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.

Challenge

Do it in-place and without extra memory.

Notice

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

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

public class Solution {     /*      * @param A: An integer array.      * @return: nothing      */     public void rerange(int[] A) {         if (A == null || A.length < 2) {             return;         }                   int pivot = partition(A);         int numNegative = pivot + 1;         int numPositive = A.length - pivot - 1;                   if (numNegative == numPositive - 1) {             interleave(A, 0, A.length - 2);         } else if (numNegative == numPositive + 1 ) {             interleave(A, 1, A.length - 1);         } else {             interleave(A, 0, A.length - 1);         }     }           private int partition(int[] A) {         int start = 0;         int end = A.length - 1;                   while (start <= end) {             while (start <= end && A[start] < 0) {                 start++;             }                           while (start <= end && A[end] >= 0) {                 end--;             }                           if (start <= end) {                 swap(A, start, end);                 start++;                 end--;             }         }                   return end;     }           private void interleave(int[] A, int start, int end) {         while (start < end) {             swap(A, start, end);             start += 2;             end -= 2;         }     }           private void swap(int[] A, int i, int j) {         int temp = A[i];         A[i] = A[j];         A[j] = temp;     } }