計數(shù)排序
題目
給定一個包含紅色逛拱、白色和藍(lán)色，一共 n 個元素的數(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)階：
一個直觀的解決方案是使用計數(shù)排序的兩趟掃描算法活合。
首先，迭代計算出0物赶、1 和 2 元素的個數(shù)白指，然后按照0、1酵紫、2的排序侵续，重寫當(dāng)前數(shù)組。
你能想出一個僅使用常數(shù)空間的一趟掃描算法嗎憨闰？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sort-colors
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有状蜗。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處鹉动。
解答
我的垃圾答案(本質(zhì)只能應(yīng)付這一題)：
`
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
"""使用計數(shù)排序"""
maxnum=max(nums)
minnum=min(nums)
listcount=[0 for i in range(maxnum+1)]
for i in range(len(nums)):
listcount[nums[i]]=listcount[nums[i]]+1
for i in range(1,len(listcount)):
listcount[i]=listcount[i]+listcount[i-1]
for i in range(len(listcount)-1,0,-1):
for j in range(listcount[i-1],listcount[i]):
nums[j]=i
for i in range(0,listcount[0]):
nums[i]=0
`
其他答案（模仿指針）
`
def sortColors(self, nums: List[int]) -> None:
# 對于所有 idx < p0 : nums[idx < p0] = 0
# curr是當(dāng)前考慮元素的下標(biāo)
p0 = curr = 0
# 對于所有 idx > p2 : nums[idx > p2] = 2
p2 = len(nums) - 1
while curr <= p2:
if nums[curr] == 0:
nums[p0], nums[curr] = nums[curr], nums[p0]
p0 += 1
curr += 1
elif nums[curr] == 2:
nums[curr], nums[p2] = nums[p2], nums[curr]
p2 -= 1
else:
curr += 1
`
反思
躺平轧坎，學(xué)不來，想不到泽示「籽哭泣。
