題目
給出一個(gè)含有正整數(shù)和負(fù)整數(shù)的數(shù)組鹃觉，重新排列成一個(gè)正負(fù)數(shù)交錯(cuò)的數(shù)組熄攘。
注意事項(xiàng)
不需要保持正整數(shù)或者負(fù)整數(shù)原來(lái)的順序。
樣例
給出數(shù)組[-1, -2, -3, 4, 5, 6]，重新排序之后县匠，變成[-1, 5, -2, 4, -3, 6]或者其他任何滿足要求的答案
分析
最簡(jiǎn)單的思路顯然是用兩個(gè)數(shù)組記錄正數(shù)和負(fù)數(shù)，最后在遍歷一遍即可
要求原地完成的思路：
兩根指針撒轮，首先判斷正數(shù)多還是負(fù)數(shù)多乞旦，并把多的那一部分移到后半部分，最后兩根指針?lè)謩e遞增二交換即可
具體思路看代碼注釋
代碼
class Solution {
/**
* @param A: An integer array.
* @return: void
*/
public int[] rerange(int[] A) {
// Check the input parameter.
if(A == null || A.length < 3)
return A;
int n = A.length;
int countPositive = 0;//計(jì)算正數(shù)的個(gè)數(shù)
// store the positive numbers index.
int positiveIndex = 0;
int pos = 1;
int neg = 0;
for(int i=0;i<n;i++) {
if(A[i] > 0) {
// Put all the positive numbers at in the left part.
swap(A,positiveIndex++,i);
countPositive++;
}
}
if(countPositive > n/2) {
// If positive numbers are more than negative numbers,
// Put the positive numbers at first.
pos = 0;
neg = 1;
// Reverse the array.
int left = 0;
int right = n-1;
while(left < right) {
swap(A,left,right);
left++;
right--;
}
}
while(pos < n && neg <n) {
while(pos<n && A[pos]>0)
pos +=2;
while(neg<n && A[neg]<0)
neg +=2;
if(neg >= n || pos>=n)
break;
swap(A,pos,neg);
}
// Reorder the negative and the positive numbers.
// Should move if it is in the range.
// Should move if it is in the range.
return A;
}
public void swap(int[] A, int l, int r) {
int temp = A[l];
A[l] = A[r];
A[r] = temp;
}
}
