Interleaving Array

给出一个含有正整数和负整数的数组,重新排列成一个正负数交错的数组。

样例

给出数组[-1, -2, -3, 4, 5, 6],重新排序之后,变成[-1, 5, -2, 4, -3, 6]或者其他任何满足要求的答案

注意

不需要保持正整数或者负整数原来的顺序。

挑战

原地完成,没有额外的空间

Solution

这道题没有给出正数、负数谁多谁少,所以需要先统计数量,数量多的要包着数量少的,然后数组尾部全是数量多的数

Complexity

时间复杂度 O(n),空间复杂度 O(1)

Code

class Solution {
    /**
     * @param A: An integer array.
     * @return: void
     */
    public void rerange(int[] A) {
        int posNum = 0, negNum = 0;
        for (int elem : A) {
            if (elem < 0) {
                negNum++;
            }
            else {
                posNum++;
            }
        }
        int posInd = 1, negInd = 0;
        if (posNum > negNum) {
            negInd = 1;
            posInd = 0;
        }
        while (posInd<A.length && negInd<A.length) {
            while (posInd < A.length && A[posInd] > 0) {
                posInd += 2;
            }
            while (negInd < A.length && A[negInd] < 0) {
                negInd += 2;
            }
            if (posInd<A.length && negInd<A.length) {
                swap(A, posInd, negInd);
            }
        }
        return ;
   }

   public void swap(int[] A, int l, int r) {
       int temp = A[l];
       A[l] = A[r];
       A[r] = temp;
   }
}