Interleaving Positive and Negative Numbers

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

Given [-1, -2, -3, 4, 5, 6], after re-range, it will be [-1, 5, -2, 4, -3, 6] or any other legal answer.

Do it in-place and without extra memory.

SOLUTION 1:

1. 先用parition把数组分为左边为负数，右边为正数。

2. 如果负数比较多，把多余的负数与尾部的值交换。（这样多余的数会放在数组的末尾）

3. left 指向数组的左边，right指向数组的右边减掉多余的数。

4. 第3步中，根据是正数多，还是负数多，起始位置要变一下。正数多，我们希望开始的是正数：

例如 3 -1 2

负数多，我们希望开始的是负数，如 -1 3 -2

5. 不断交换left, right指针，并一次前进步长2. 直到left, right 相遇。

 1 class Solution { 2    /** 3      * @param A: An integer array. 4      * @return an integer array 5      */ 6     // SOLUTION 2: 判断正数多还是负数多。  7     public static int[] rerange(int[] A) { 8         // write your code here 9         10         // Check the input parameter.11         if (A == null || A.length == 0) {12             return A;13         }14         15         int len = A.length;16         17         int left = -1;18         int right = A.length;19         20         // divide the negative and positive integers.21         while (true) {22             while (left < A.length - 1 && A[++left] < 0);23             24             while (left < right && A[--right] > 0);25             26             if (left >= right) {27                 break;28             }29             30             swap(A, left, right);31         }32         33         // LEFT: point to the first positive number.34         int negNum = left;35         int posNum = len - left;36         37         int les = Math.min(negNum, posNum);38         int dif = Math.abs(negNum - posNum);39         40         // 如果负数比较多，把多的负数扔到后面去41         if (negNum > posNum) {42             int cnt = dif;43             int l = les;44             int r = len - 1;45             while (cnt > 0) {46                 swap(A, l, r);47                 l++;48                 r--;49                 cnt--;50             }51             52             // 负数多的时候，负数在前，反之，正数在前53             left = -1;54             // 跳过右边不需要交换的值55             right = A.length - dif;56         } else {57             // 正数在前58             left = -2;59             // 跳过右边不需要交换的值60             right = A.length - dif + 1;61         }62         63         /*64           -1 -2 -5 -6  3  4  les = 2;65           4  -2 -5 -6  3 -166         */67         // swap the negative and the positive68         while (true) {69             left += 2;70             right -= 2;71             72             if (left >= les) {73                 break;74             }75             swap(A, left, right);76         }77 78         return A;79    }80    81    public static void swap(int[] A, int n1, int n2) {82        int tmp = A[n1];83        A[n1] = A[n2];84        A[n2] = tmp;85    }86 }