Interleaving Positive and Negative Numbers

Given an array with positive and negative integers. Re-range it to interleaving with positive and 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.

Solution

Two pointers = , pay more attention to slide while.

while left < right

while slide left

while slide right

if left < right:

switch:

这道题没有给出正数、负数谁多谁少，所以需要先统计数量，数量多的要包着数量少的，然后数组尾部全是数量多的数

(1) 统计出来多少个负数跟正数

(2) 保证多的数从0开始，少的那，从索引1开始

(3) 左右指针从左侧出发，每次错开都跳两个

class Solution:
    """
    @param A: An integer array.
    @return nothing
    """
    def rerange(self, A):
        posNum, negNum = 0, 0 #统计正数负数各有多少
        for x in A:
            if x > 0:
                posNum += 1
            else:
                negNum += 1
        posInd, negInd = 1, 0
        if posNum > negNum: # 正数多则正数从索引0开始包含负数
            posInd = 0
            negInd = 1

        while posInd < len(A) and negInd < len(A): #从同一侧开始做双指针推进。
            while negInd < len(A) and A[negInd] <= 0:
                negInd += 2

            while posInd < len(A) and A[posInd] > 0:
                posInd += 2

            if posInd < len(A) and negInd < len(A):
                A[posInd], A[negInd] = A[negInd], A[posInd]
                posInd += 2
                negInd += 2
        return A