[leetcode]Interleaving Positive and Negative Numbers

2018年05月13日 ⁄ 综合 ⁄ 共 765字 ⁄ 字号 评论关闭

Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.

Note

You are not necessary to keep the original order or 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 legal answer.

Challenge

Do it in-place and without extra memory.

```class Solution {
/**
* @param A: An integer array.
* @return an integer array
*/
public int[] rerange(int[] A) {
if(A==null || A.length<=1)
return A;

int s = 0;
int p1 = -1;
int p2 = -1;
for(int i=0;i<A.length;i++){
if(p1 == -1 && A[i] > 0)
p1 = i;
if(p1 == -1 && A[i] < 0)
p2 = i;
s += A[i] > 0?1:-1;
}
if(s<0)
p1 = p2;

int tmp = A[0];
A[0] = A[p1];
A[p1] = tmp;

for(int i=1;i<A.length;i++){
int j=i;
while(j<A.length && A[j] * A[i-1]>0)
j++;
if(j>i && j<A.length){
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
return A;
}
}
```

【上篇】
【下篇】