75. Sort Colors
MediumDescription
給定陣列
nums，其中只包含 0、1、2（代表紅、白、藍），原地排序使得相同顏色相鄰，順序為 0、1、2。不能使用內建排序函式。
Example:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Intuition#
核心思路：Dutch National Flag（荷蘭國旗問題）——用三個指標將陣列分為三個區域：0 區、1 區、2 區。
- 三個指標：
lo指向 0 區的右邊界，hi指向 2 區的左邊界，mid是當前掃描位置 - 遇到 0 往前交換，遇到 2 往後交換，遇到 1 跳過
Approaches#
1: 兩次遍歷（計數排序）#
- 概念: 第一次遍歷統計 0、1、2 的數量，第二次遍歷按順序填入
- 時間複雜度:
O(n)- 兩次遍歷 - 空間複雜度:
O(1)- 只用三個計數器
class Solution {
fun sortColors(nums: IntArray) {
val count = IntArray(3)
for (num in nums) count[num]++
var idx = 0
for (color in 0..2) {
repeat(count[color]) {
nums[idx++] = color
}
}
}
}⭐2: Dutch National Flag（一次遍歷）#
- 概念: 三指標分區——
lo追蹤 0 的右邊界，hi追蹤 2 的左邊界，mid掃描 - 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
O(1)- 原地交換
class Solution {
fun sortColors(nums: IntArray) {
var lo = 0
var mid = 0
var hi = nums.lastIndex
while (mid <= hi) {
when (nums[mid]) {
0 -> {
nums[mid] = nums[lo].also { nums[lo] = nums[mid] }
lo++
mid++
}
1 -> {
mid++
}
2 -> {
nums[mid] = nums[hi].also { nums[hi] = nums[mid] }
hi--
// mid 不動，因為交換過來的值還沒檢查
}
}
}
}
}注意：遇到 2 交換後
mid不能前進，因為從hi換過來的值還未被檢查。遇到 0 交換後mid可以前進，因為lo左邊只可能是 0 或已處理的 1。
🔑 Takeaways#
- Pattern: Dutch National Flag 三向切分，是 Quick Sort 三向切分的基礎
- 關鍵技巧: 關鍵在於理解何時
mid前進、何時不動；此演算法由 Dijkstra 提出，也用於 Quick Sort 處理大量重複元素