原題

給出一個(gè)含有正整數(shù)和負(fù)整數(shù)的數(shù)組，重新排列成一個(gè)正負(fù)數(shù)交錯(cuò)的數(shù)組。

樣例
給出數(shù)組[-1, -2, -3, 4, 5, 6]，重新排序之后，變成[-1, 5, -2, 4, -3, 6]
或者其他任何滿足要求的答案

解題思路

• 掃第一遍，確定正數(shù)多還是負(fù)數(shù)多，多的放在0位
• partition數(shù)組，前面都是正數(shù)后面都睡負(fù)數(shù)，或者相反，根據(jù)誰多
• 兩步一跳，生成需要的正負(fù)間隔的數(shù)組

完整代碼

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