Interleaving Positive and Negative Numbers
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.
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.
class Solution {
/**
* @param A: An integer array.
* @return: void
*/
public void rerange(int[] A) {
if (A == null || A.length == 0) {
return;
}
int positiveCount = 0, negativeCount = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] > 0) {
positiveCount++;
} else {
negativeCount++;
}
}
int negativeIndex = 0, positiveIndex = 1;
if (positiveCount > negativeCount) {
negativeIndex = 1;
positiveIndex = 0;
}
while (negativeIndex < A.length && positiveIndex < A.length) {
while (negativeIndex < A.length && A[negativeIndex] < 0) {
negativeIndex += 2;
}
while (positiveIndex < A.length && A[positiveIndex] > 0) {
positiveIndex += 2;
}
if (negativeIndex < A.length && positiveIndex < A.length) {
int temp = A[negativeIndex];
A[negativeIndex] = A[positiveIndex];
A[positiveIndex] = temp;
negativeIndex += 2;
positiveIndex += 2;
}
}
}
}
Hope this helps,
Michael