75. Sort Colors

给出一个由红、白、蓝三种颜色组成的数组，把相同颜色的元素放到一起，并整体按照红、白、蓝的顺序。用0表示红色，1表示白色，2表示蓝色

思路： 计数排序，计数排序，先计算每个颜色的数量，然后逐个往原来的数组填充直到达到数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # 5 star, 
        count = [0] * 3
        for i in nums:
            count[i] += 1
        index = 0
        for i in range(3):
            for j in range(count[i]):
                nums[index] = i
                index += 1

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func sortColors(nums []int)  {
	count := make([]int, 3)
	for _, num := range nums {
		count[num] += 1
	}
	index := 0
	for idx, _ := range count {
		for count[idx] > 0 {
			nums[index] = idx
			index++
			count[idx] -= 1
		}
	}

}