【題目描述】
給定一個(gè)包含紅色篱竭、白色和藍(lán)色，一共 n 個(gè)元素的數(shù)組势腮，原地對它們進(jìn)行排序，使得相同顏色的元素相鄰歹茶，并按照紅色、白色、藍(lán)色順序排列惊豺。
此題中燎孟，我們使用整數(shù) 0、 1 和 2 分別表示紅色尸昧、白色和藍(lán)色揩页。
注意:
不能使用代碼庫中的排序函數(shù)來解決這道題。
【示例】
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
【進(jìn)階】
一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法烹俗。
首先爆侣，迭代計(jì)算出0、1 和 2 元素的個(gè)數(shù)衷蜓，然后按照0累提、1尘喝、2的排序磁浇，重寫當(dāng)前數(shù)組。
你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎朽褪？
代碼實(shí)現(xiàn)
【解1】 看看就行啦 ??
func sortColors(_ nums: inout [Int]) {
var zero = 0,one = 0
for n in nums {
if n == 0 {
zero+=1
} else if n == 1 {
one+=1
}
}
let two = nums.count-zero-one
var i = 0
for _ in 0..<zero {
nums[i] = 0
i+=1
}
for _ in 0..<one {
nums[i] = 1
i+=1
}
for _ in 0..<two {
nums[i] = 2
i+=1
}
}
【解2】
思路：
1置吓、使用三個(gè)指針來標(biāo)識數(shù)組左邊、右邊和當(dāng)前的index缔赠；
2衍锚、當(dāng)nums[current]為0時(shí)，nums[left]和nums[current]交換嗤堰，left++戴质，current++；
3踢匣、當(dāng)nums[current]為2時(shí)告匠，nums[right]和nums[current]交換，right--;因?yàn)橛疫吔粨Q完后全是2离唬，所以right--后专，跟左邊全是0后left++一個(gè)道理，這里current不需要++输莺，因?yàn)槟悴恢捞鎿Q后的nums[current]是幾戚哎；
4、當(dāng)nums[current] == 1時(shí)嫂用，current++即可
5型凳、時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)
func sortColors(_ nums: inout [Int]) {
var left = 0,right = nums.count-1,current = 0
var tmp = 0
while current <= right {
if nums[current] == 0 {
tmp = nums[left]
nums[left] = nums[current]
nums[current] = tmp
current+=1
left+=1
} else if nums[current] == 2 {
tmp = nums[right]
nums[right] = nums[current]
nums[current] = tmp
right-=1
} else {
current+=1
}
}
}
