前往
大廳
主題

LeetCode - 75. Sort Colors 解題心得

Not In My Back Yard | 2022-04-14 00:00:11 | 巴幣 100 | 人氣 283

題目連結:


題目意譯:
給定一個有著 n 個塗成紅、白或藍色的物件陣列 nums,原地(In-place)將它們排序,使得相同顏色的物件是相鄰的,且顏色的順序為紅、白以及藍色。

我們將使用整數 0 、 1 和 2 來依序代表紅、白以及藍色。

你必須在不使用函式庫的排序函式的情況下解出本題。

限制:
n == nums.length
1 ≦ n ≦ 300
nums[i] 只會是 0 、 1 或是 2。

進階: 你可以想出只掃過一次(One-pass)並且只使用常數大小的額外空間之的演算法嗎?



範例測資:
範例 1:
輸入: nums = [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]

範例 2:
輸入: nums = [2,0,1]
輸出: [0,1,2]


解題思維:
類似這題的想法——利用兩個變數 L 、 R 來表示「下一個」0 和 2 可以放的位置。一開始 L = 0 、 R = nums.size() - 1,因為 0 要在左側、 1 在中間,而 2 在右側。

接著利用一變數 i(一開始值為 0)來掃過 nums 中所有數字——即重複以下步驟直到 i > R 為止(此時即代表所有數字都掃過一次了):
如果 nums[i] 為 0,則將 nums[L] 和 nums[i] 交換,並將 L 和 i 都加 1;
如果 nums[i] 為 2,則將 nums[R] 和 nums[i] 交換,並將 R 減去 1;
(這邊 R 的情況不將 i 一起加 1 是因為我們是由左至右掃,我們只能保證索引值 0 ~ L - 1 的值都是「0」。因此 i 之值將至少為 L。但是從 nums[R] 交換過來的數字我們不得而知)
如果 nums[i] 為 1,則將 i 加 1 即可。

全部掃完之後,nums[0] ~ nums[L - 1] 都是「0」(如果 L = 0,則代表 nums 中沒有「0」)、nums[R + 1] ~ nums[nums.size() - 1] 都是「2」(如果 R = nums.size() - 1,則代表 nums 中沒有「2」)。除此之外的位置都會是「1」,因此此時的 nums 即為所求,且滿足原本題目以及進階的要求。




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

創作回應

更多創作