Interleaving Positive and Negative Numbers
原题链接 ： http://lintcode.com/zh-cn/problem/interleaving-positive-and-negative-numbers/
Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.
注意
You are not necessary to keep the original order or positive integers or negative integers.
样例
Given [-1, -2, -3, 4, 5, 6], after re-range, it will be [-1, 5, -2, 4, -3, 6] or any other legal answer.
挑战
Do it in-place and without extra memory.
SOLUTION 1:
1. 先用parition把数组分为左边为负数，右边为正数。
2. 如果负数比较多，把多余的负数与尾部的值交换。（这样多余的数会放在数组的末尾）
3. left 指向数组的左边，right指向数组的右边减掉多余的数。
4. 第3步中，根据是正数多，还是负数多，起始位置要变一下。正数多，我们希望开始的是正数：
例如 3 -1 2
负数多，我们希望开始的是负数，如 -1 3 -2
5. 不断交换left, right指针，并一次前进步长2. 直到left, right 相遇。
class Solution {
/**
* @param A: An integer array.
* @return an integer array
*/
// SOLUTION 2: 判断正数多还是负数多。
public static int[] rerange(int[] A) {
// write your code here
// Check the input parameter.
if (A == null || A.length == 0) {
return A;
}
int len = A.length;
int left = -1;
int right = A.length;
// divide the negative and positive integers.
while (true) {
while (left < A.length - 1 && A[++left] < 0);
while (left < right && A[--right] > 0);
if (left >= right) {
break;
}
swap(A, left, right);
}
// LEFT: point to the first positive number.
int negNum = left;
int posNum = len - left;
int les = Math.min(negNum, posNum);
int dif = Math.abs(negNum - posNum);
// 如果负数比较多，把多的负数扔到后面去
if (negNum > posNum) {
int cnt = dif;
int l = les;
int r = len - 1;
while (cnt > 0) {
swap(A, l, r);
l++;
r--;
cnt--;
}
// 负数多的时候，负数在前，反之，正数在前
left = -1;
// 跳过右边不需要交换的值
right = A.length - dif;
} else {
// 正数在前
left = -2;
// 跳过右边不需要交换的值
right = A.length - dif + 1;
}
/*
-1 -2 -5 -6 3 4 les = 2;
4 -2 -5 -6 3 -1
*/
// swap the negative and the positive
while (true) {
left += 2;
right -= 2;
if (left >= les) {
break;
}
swap(A, left, right);
}
return A;
}
public static void swap(int[] A, int n1, int n2) {
int tmp = A[n1];
A[n1] = A[n2];
A[n2] = tmp;
}
}
SOLUTION 2(December 23th Refresh)：
1. 扫一次确定是正数多还是负数多
2. 把奇数索引的所有的数字进行partition，如果是正数多，把正数放在后面，否则负数放在后面。
3. 令Index 1 = 奇数列，index 2 = 偶数列，扫描一次，遇到不符合正负条件的数字进行交换即可
public static void swap(int[] A, int n1, int n2) {
int tmp = A[n1];
A[n1] = A[n2];
A[n2] = tmp;
}
/*
Solution 2:
*/
public static int[] rerange(int[] A) {
// write your code here
// Check the input parameter.
if (A == null || A.length <= 2) {
return A;
}
int len = A.length;
int cntPositive = 0;
for (int num: A) {
if (num > 0) {
cntPositive++;
}
}
// If positive numbers are more than negative numbers,
// Put the positive numbers at first.
int posPointer = 1;
int negPointer = 0;
// means
boolean pos = false;
if (cntPositive > A.length / 2) {
// Have more Positive numbers;
posPointer = 0;
negPointer = 1;
pos = true;
}
int i = 1;
int j = len - 2;
if (pos) {
while (true) {
// Put the positive numbers at the end.
if (i < len && A[i] < 0) {
i += 2;
}
if (j > i && A[j] > 0) {
j -= 2;
}
if (i >= j) {
break;
}
swap(A, i, j);
}
} else {
while (true) {
// Put the negative numbers at the end.
if (i < len && A[i] > 0) {
i += 2;
}
if (j > i && A[j] < 0) {
j -= 2;
}
if (i >= j) {
break;
}
swap(A, i, j);
}
}
// Reorder the negative and the positive numbers.
while (true) {
// Should move if it is in the range.
while (posPointer < len && A[posPointer] > 0) {
posPointer += 2;
}
// Should move if it is in the range.
while (negPointer < len && A[negPointer] < 0) {
negPointer += 2;
}
if (posPointer >= len || negPointer >= len) {
break;
}
swap(A, posPointer, negPointer);
}
return A;
}
SOLUTION 3(December 23th Refresh):
在SOL2的基础上改进：
1. 在统计正负数个数时，把负数放在最后。
2. 如果发现正数比较多，把数列翻转。
3. 令Index 1 = 奇数列，index 2 = 偶数列，扫描一次，遇到不符合正负条件的数字进行交换即可
/*
Solution 3:
*/
public static int[] rerange(int[] A) {
// write your code here // Check the input parameter.
if (A == null || A.length <= 2) {
return A;
} int len = A.length; int cntPositive = 0; // store the positive numbers index.
int i1 = 0; for (int i2 = 0; i2 < len; i2++) {
if (A[i2] > 0) {
cntPositive++; // Put all the positive numbers at in the left part.
swap(A, i1++, i2);
}
} // If positive numbers are more than negative numbers,
// Put the positive numbers at first.
int posPointer = 1;
int negPointer = 0; if (cntPositive > A.length / 2) {
// Have more Positive numbers;
posPointer = 0;
negPointer = 1; // Reverse the array.
int left = 0;
int right = len -1;
while (left < right) {
int tmp = A[left];
A[left] = A[right];
A[right] = tmp;
left++;
right--;
}
} // Reorder the negative and the positive numbers.
while (true) {
// Should move if it is in the range.
while (posPointer < len && A[posPointer] > 0) {
posPointer += 2;
} // Should move if it is in the range.
while (negPointer < len && A[negPointer] < 0) {
negPointer += 2;
} if (posPointer >= len || negPointer >= len) {
break;
} swap(A, posPointer, negPointer);
} return A;
}
SOLUTION 4(December 23th Refresh):
在SOL3的基础上改进：
翻转数列的一步修改为：把右边的负数移动到左边即可。可以优化复杂度。其它与SOL3一致。
感谢Lansheep大神提供思路！
/*
Solution 4:
把reverse的步骤简化了一下
*/
public static int[] rerange(int[] A) {
// write your code here // Check the input parameter.
if (A == null || A.length <= 2) {
return A;
} int len = A.length; int cntPositive = 0; // store the positive numbers index.
int i1 = 0; for (int i2 = 0; i2 < len; i2++) {
if (A[i2] > 0) {
cntPositive++; // Put all the positive numbers at in the left part.
swap(A, i1++, i2);
}
} // If positive numbers are more than negative numbers,
// Put the positive numbers at first.
int posPointer = 1;
int negPointer = 0; if (cntPositive > A.length / 2) {
// Have more Positive numbers;
posPointer = 0;
negPointer = 1; // Reverse the array.
int left = 0;
int right = len -1;
while (right >= cntPositive) {
swap(A, left, right);
left++;
right--;
}
} // Reorder the negative and the positive numbers.
while (true) {
// Should move if it is in the range.
while (posPointer < len && A[posPointer] > 0) {
posPointer += 2;
} // Should move if it is in the range.
while (negPointer < len && A[negPointer] < 0) {
negPointer += 2;
} if (posPointer >= len || negPointer >= len) {
break;
} swap(A, posPointer, negPointer);
} return A;
}
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/array/Rerange.java