i144.Interleaving_Positive_and_Negative_Numbers.md

i144 · Interleaving Positive and Negative Numbers

Medium

https://www.lintcode.com/problem/144/

Description

Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.

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

Example

Example 1

Input : [-1, -2, -3, 4, 5, 6] Outout : [-1, 5, -2, 4, -3, 6] Explanation : any other reasonable answer.

Challenge

Do it in-place and without extra memory.

Tags

• Opposite Direction Two Pointers
• Two Pointers

Related Problems

• 31 Partition Array Medium

python

class Solution:
    """
    @param: A: An integer array.
    @return: nothing
    """
    def rerange(self, A):
        # 1. count positive and negative numbers 
        # 2. parition them, which more will be put at left. Eg. [pos, pos, pos, neg, neg]
        # 3. 2 pointers swap them
        
        pos_ctr, neg_ctr = 0, 0
        for elem in A:
            if elem > 0:
                pos_ctr += 1
            else:
                neg_ctr += 1
        
        pos_first = 1 if pos_ctr > neg_ctr else -1
        self.parition(A, pos_first)
        self.interleav(A, pos_ctr == neg_ctr)

    def parition(self, A, pos_first):
        left, right = 0, len(A) - 1
        pivotvalue = A[(left + right) // 2]
        while left <= right:
            while left <= right and A[left] * pos_first > 0:
                left += 1
            while left <= right and A[right] * pos_first < 0:
                right -= 1
            if left <= right:
                A[left], A[right] = A[right], A[left]
                left += 1
                right -= 1

    def interleav(self, A, has_same_leng):
        left, right = 0, len(A) - 1
        if not has_same_leng:
            left = 1

        while left < right:
            A[left], A[right] = A[right], A[left]
            left += 2
            right -= 2