Question

link

给一个包含正负整数的数组，要求对这个数组中的数进行重新排列，使得其正负交替出现。首先出现负数，然后是正数，然后是负数。有多余的数的一方，就放在末尾。

如 [1, 2, 3, -4]->[-4, 1, 2, 3]，[1,-3,2,-4,-5]->[-3,1,-4,2,-5]. 要求使用O(1)的额外空间。

如果需要保持正数序列和负数序列各自原来的顺序，如何做？

如果不需要保持正数序列和负数序列各自原来的顺序，如何做？

Solution

I only solve this question if we do not have to keep the original ordering.

Basically, 2 pointers search from beginning to end. If there’re more + than -, move the extra positive values to the back of the array. Vice versa.

Code

written by me

public void solve(int[] A) {
	int len = A.length;
	int neg = 0;
	int pos = 1;
	while (neg < len || pos < len) {

		while (neg < len && A[neg] < 0) {
			neg += 2;
		}
		while (pos < len && A[pos] > 0) {
			pos += 2;
		}
		// neg points to a positive value
		// pos points to a negative value
		// swap them (if they're valid position)
		if (neg >= len && pos >= len) {
			return;
		} else if (neg >= len) {
			// neg is done, there's more - then +
			// put all negative values pointed by pos to the back
			int right = len - 1;
			if (right % 2 == 0) {
				right--;
			}
			while (pos < right) {
				while (pos < len && A[pos] > 0) {
					pos += 2;
				}
				while (right >= 0 && A[right] < 0) {
					right -= 2;
				}
				// pos point to a negative value, right to positive value
				if (pos > right) {
					break;
				} else {
					swap(A, pos, right);
				}
			}
			return;
		} else if (pos >= len) {
			// pos is done, there's more + then -
			int right = len - 1;
			if (right % 2 == 1) {
				right--;
			}
			while (neg < right) {
				while (neg < len && A[neg] < 0) {
					neg += 2;
				}
				while (right >= 0 && A[right] > 0) {
					right -= 2;
				}
				if (neg > right) {
					break;
				} else {
					swap(A, neg, right);
				}
			}
			return;
		} else {
			swap(A, neg, pos);
		}
	}
}

private void swap(int[] array, int a, int b) {
	int temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}