雙指針應用: 按照正負號，重組陣列Rearrange Elements by Sign_Leetcode #2149

Tim Mossholder on Unsplash

題目敘述

題目給定我們一個輸入陣列nums

要求我們以正、負交叉排列的方式重組陣列，並且必須保持原本的相對順序。

並且以陣列的形式輸出返回答案。

例[5, 1, -2, -3] 重排後為 [5, -2, 1, -3]

題目的原文敘述

測試範例

Example 1:

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.  

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

約束條件

Constraints:

• 2 <= nums.length <= 2 * 10^5

輸入陣列長度介於2 ~ 二十萬 之間。

• nums.length is even

輸入陣列長度保證是偶數。

• 1 <= |nums[i]| <= 10^5

輸入陣列的絕對值介於1 ~ 十萬 之間。

• nums consists of equal number of positive and negative integers.

題目保證 輸入陣列裡的正數和負數的數量一定一樣多。

演算法 雙指針 two-pointers

題目已經指定依照 正、負、正、負 交叉前進的順序重新排列，而且又要保持原本的相對順序。

那麼，我們可以維護一組 雙指針 來記錄每回合對應到的寫入位置。

正值的寫入位置初始化為0 (因為正,負,正,負，正值一定是偶數位置)

負值的寫入位置初始化為1 (因為正,負,正,負，負值一定是奇數位置)

建造一個迴圈，從左到右掃描過輸入陣列nums的每個元素

用signbit當作索引，去取得對應的指針和寫入位置。

寫入之後，把寫入位置+2 移動到下一次新的寫入位置。

(因為正、負、正、負 交叉前進，下一次的寫入位置總是往前移動兩格。)

示意圖

程式碼 雙指針 two-pointers

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        
        output = [ 0 for _ in range( len(nums) )]

        # pointers for positive number, negative number
        pointers = [0, 1]

        for number in nums:
            
            write_position = pointers[ number < 0 ]
            output[ write_position ] = number
            pointers[ number < 0 ] += 2

        return output

複雜度分析 雙指針 two-pointers

時間複雜度:

從左到右一次線性掃描，所需時間為O(n)。

空間複雜度:

扣掉固定輸出成本output array，

其他用到的都是固定尺寸的臨時變數，所需的輔助空間為O(1)。

關鍵知識點

題目已經指定依照 正、負、正、負 交叉前進的順序重新排列，而且又要保持原本的相對順序。

那麼，我們可以維護一組 雙指針 來記錄每回合對應到的寫入位置。

正值的寫入位置初始化為0 (因為正,負,正,負，正值一定是偶數位置)

負值的寫入位置初始化為1 (因為正,負,正,負，負值一定是奇數位置)

用signbit當作索引，去取得對應的指針和寫入位置。

Reference:

[1] Rearrange Array Elements by Sign - LeetCode