原题
给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。
样例
给出数组[-1, -2, -3, 4, 5, 6]，重新排序之后，变成[-1, 5, -2, 4, -3, 6]
或者其他任何满足要求的答案
解题思路
- 扫第一遍，确定正数多还是负数多，多的放在0位
- partition数组，前面都是正数后面都睡负数，或者相反，根据谁多
- 两步一跳，生成需要的正负间隔的数组
完整代码
class Solution:
"""
@param A: An integer array.
@return nothing
"""
def rerange(self, A):
# write your code here
pos, neg = 0, 0
for num in A:
if num > 0:
pos += 1
else:
neg += 1
if pos > neg:
left, right = 0, len(A) - 1
while left < right:
while A[left] > 0 and left < right:
left += 1
while A[right] < 0 and left < right:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
left, right = 1, len(A) - 1
while left < right:
A[left], A[right] = A[right], A[left]
left += 2
right -= 2
else:
left, right = 0, len(A) - 1
while left < right:
while A[left] < 0 and left < right:
left += 1
while A[right] > 0 and left < right:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
if pos == neg:
left, right = 1, len(A) - 2
else:
left, right = 1, len(A) - 1
while left < right:
A[left], A[right] = A[right], A[left]
left += 2
right -= 2
