前往
大廳
主題

LeetCode - 2149. Rearrange Array Elements by Sign 解題心得

Not In My Back Yard | 2022-09-01 12:00:09 | 巴幣 0 | 人氣 197

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的偶數長度之整數陣列 nums,其由等量的正整數以及負整數組成。

你應重新排列這些元素使得修改後的陣列符合以下條件:
每個相鄰整數有著相反的正負號。
對於同一個正負號的所有整數,它們的順序應保持於原先在 nums 中的順序。
重新排列的陣列開始於一個正整數。

回傳重新排列後滿足以上條件的陣列。

限制:
2 ≦ nums.length ≦ 2 × 10 ^ 5
nums.length 為偶數
1 ≦ |nums[i]| ≦ 10 ^ 5
nums 由等量的正整數以及負整數組成。



範例測資:
範例 1:
輸入: nums = [3,1,-2,-5,2,-4]
輸出: [3,-2,1,-5,2,-4]
解釋:
nums 中的正整數為 [3,1,2]。負整數為 [-2,-5,-4]。
唯一一個重新排列並滿足所有條件的方式為 [3,-2,1,-5,2,-4]。
其他方式如 [1,-2,2,-5,3,-4] 、 [3,1,2,-2,-5,-4] 、 [-2,3,-5,1,-4,2] 是不正確的,因為它們不符合其中一個或多個條件。

範例 2:
輸入: nums = [-1,1]
輸出: [1,-1]
解釋:
1 是唯一一個正整數,而 -1 是唯一一個負整數。
因此 nums 將重新排列成 [1,-1]。


解題思維:
其實就跟這題的想法很類似,只是把整個陣列的索引值分成偶數(0 、 2 、 4 、……)以及奇數(1 、 3 、 5 、……)來分別放置正整數以及負整數。也就是,我們掃過一次 nums,每次遇到正整數就是依序放到(實際上是「交換」,因為直接取代數值會影響結果)索引值 0 、 2 、 4 、……之位置;相似地,每次遇到負整數就是依序放到索引值 1 、 3 、 5 、……之位置。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作