[LintCode] Interleaving Positive and Negative Numb

calx 發(fā)布于2019-08-14 15:22 / 1377人閱讀

摘要：注意，若正數(shù)多于負(fù)數(shù)，則序列以正數(shù)開始，正數(shù)結(jié)束。所以先統(tǒng)計正數(shù)個數(shù)，若超過序列長度的一半，則正指針從開始，反之則負(fù)指針從開始。注意交換函數(shù)的形式，必須是交換指針?biāo)笖?shù)字的值，而非坐標(biāo)。

Problem

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.

Challenge

Do it in-place and without extra memory.

Note

典型雙指針題目，兩個指針分別指向交叉的正數(shù)和負(fù)數(shù)。
注意，若正數(shù)多于負(fù)數(shù)，則序列以正數(shù)開始，正數(shù)結(jié)束。所以先統(tǒng)計正數(shù)個數(shù)，若超過序列長度的一半，則正指針從0開始，反之則負(fù)指針從0開始。指針每次跳兩位，若指向的數(shù)字符號不符，則停止，交換兩指針指向的數(shù)。
注意交換函數(shù)swap()的形式，必須是交換指針?biāo)笖?shù)字的值，而非坐標(biāo)。所以下面這樣的寫法是不對的：swap(A[posIndex], A[negIndex])，因為它調(diào)用的是swap(integerA, integerB)，在交換值的同時也交換了坐標(biāo)。

Solution

class Solution {
    public void rerange(int[] A) {
        int posNum = 0, posIndex = 1, negIndex = 0;
        for (int a : A) {
            posNum += a > 0 ? 1 : 0;
        }
        if (posNum * 2 > A.length) {
            posIndex = 0;
            negIndex = 1;
        }
        while (posIndex < A.length && negIndex < A.length) {
            while (posIndex < A.length && A[posIndex] > 0) posIndex += 2;
            while (negIndex < A.length && A[negIndex] < 0) negIndex += 2;
            if (posIndex < A.length && negIndex < A.length) {
                swap(A, posIndex, negIndex);
                posIndex += 2;
                negIndex += 2;
            }
        }
    }
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}