原題
給定一個有n個對象（包括k種不同的顏色，并按照1到k進行編號）的數(shù)組锻霎，將對象進行分類使相同顏色的對象相鄰择卦，并按照1,2吼旧，...k的順序進行排序。
給出colors=[3, 2, 2, 1, 4]堕花，k=4, 你的代碼應(yīng)該在原地操作使得數(shù)組變成[1, 2, 2, 3, 4]
解題思路
- 方法1: Count sort, 掃兩遍文狱，需要O(k)的空間
- 這道題原數(shù)組還要重復(fù)利用作為bucket數(shù)組!!! 首先for循環(huán)遍歷一遍原來的數(shù)組，如果掃到a[i]缘挽，首先檢查a[a[i]]是否為正數(shù)瞄崇，如果是把a[a[i]]移動a[i]存放起來，然后把a[a[i]]記為-1(表示該位置是一個計數(shù)器壕曼，計1)苏研。 如果a[a[i]]是負數(shù)，那么說明這一個地方曾經(jīng)已經(jīng)計數(shù)了腮郊，那么把a[a[i]]計數(shù)減一摹蘑，并把color[i] 設(shè)置為0 （表示此處已經(jīng)計算過），然后重復(fù)向下遍歷下一個數(shù)轧飞，這樣遍歷原數(shù)組所有的元素過后衅鹿，數(shù)組a里面實際上存儲的每種顏色的計數(shù)，然后我們倒著再輸出每種顏色就可以得到我們排序后的數(shù)組过咬。
例子(按以上步驟運算)：
3 2 2 1 4
2 2 -1 1 4
2 -1 -1 1 4
0 -2 -1 1 4
-1 -2 -1 0 4
-1 -2 -1 -1 0
完整代碼
class Solution:
"""
@param colors: A list of integer
@param k: An integer
@return: nothing
"""
def sortColors2(self, colors, k):
if not colors:
return
for i in range(len(colors)):
while colors[i] > 0:
num = colors[i]
if colors[num - 1] > 0:
colors[i] = colors[num - 1]
colors[num - 1] = -1
elif colors[num - 1] <= 0:
colors[num - 1] -= 1
colors[i] = 0
index = len(colors) - 1
for i in range(k - 1, -1, -1):
temp = colors[i]
while temp < 0:
colors[index] = i + 1
temp += 1
index -= 1
