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 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.

分析:

其实这题思路还是很简单的,先用partition方法把数组分成两队,左边的数是小于0的数,右边的数是大于0的数。

然后,我们需要把正数插入到负数里,但是之前我们要确认正数负数哪个更多。多的要放在第一个位置。

 class Solution {
/**
* @param A: An integer array.
* @return: void
* cnblogs.com/beiyeqingteng/
*/
public void rerange(int[] A) {
if (A == null || A.length <= ) return;
int pp = partition(A); //positive number starting posisition
int np = ; // negatie number starting position
if (A.length / < pp) {
np++;
}
// put positive numbers into negative numbers
while (np <= A.length - && pp <= A.length - ) {
swap(A, np, pp);
np = np + ;
pp++;
}
} // move negative to left
private int partition(int[] A) {
int p = ;
for (int i = ; i < A.length; i++) {
if (A[i] < ) {
swap(A, i, p);
p++;
}
}
return p;
} private void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}

转载请注明出处: cnblogs.com/beiyeqingteng/

04-16 01:57