Interleaving Positive and Negative Numbers

Question

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.

Note You are not necessary to keep the original order of positive integers or negative integers.

Challenge Do it in-place and without extra memory.

Thoughts

refer

先找出正数和负数哪个多，多的那个先开始

先设定好两个指针，一个代表正数的，一个代表负数的，每次往前走2个 如果正数多，那么正数指针从0开始，负数指针从1开始

找到正数指针位置第一个为负的，负数指针位置第一个为正的，swap, 直到走到最后

Solution

class Solution:
    """
    @param A: An integer array.
    @return nothing
    """
    def rerange(self, A):
        # write your code here
        if not A:
            return

        posNum = 0
        for num in A:
            if num > 0:
                posNum += 1

        posP = 1
        negP = 0
        if posNum * 2 > len(A):
            posP = 0
            negP = 1

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

            if posP < len(A) and negP < len(A):
                tmp = A[posP]
                A[posP] = A[negP]
                A[negP] = tmp