144 · Interleaving Positive and Negative Numbers [LintCode]

 一刷

我觉得做法是对的但是没有过OC

感觉OC有问题

Time O(n)

Space O(1)

public class Solution {

/**

* @param a: An integer array.

* @return: nothing

*/

public void rerange(int[] a) {

// [-1, -2, -3, 4, 5, 6]

if (a == null) {

return;

}

int posCnt = 0;

for (int num : a) {

if (num > 0) {

posCnt++;

}

}

int negCnt = a.length - posCnt;

int posStart, negEnd;

if (posCnt == negCnt) {

posStart = 1;

negEnd = a.length - 2;

} else if (posCnt > negCnt) {

posStart = 0;

negEnd = a.length - 2;

} else {

posStart = 1;

negEnd = a.length - 1;

}

while (posStart < a.length && negEnd >= 0) {

while (posStart < a.length && a[posStart] > 0) {

posStart += 2;

}

while (negEnd >= 0 && a[negEnd] < 0) {

negEnd -= 2;

}

if (posStart < a.length && negEnd >= 0) {

int temp = a[posStart];

a[posStart] = a[negEnd];

a[negEnd] = temp;

posStart += 2;

negEnd -= 2;

}

}

}

}