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

更新於 發佈於 閱讀時間約 4 分鐘

題目敘述

題目給定我們一個輸入陣列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 移動到下一次新的寫入位置。

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


示意圖

raw-image

程式碼 雙指針 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

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多