75. Sort Colors

偷偷写一个世上最简单的题嘿嘿

问题描述

Given an array with n objects colored red, white or blue, sort them **in-place **so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
底下follow up说白了就是要求直接用 Counting Sort

什么是 Counting Sort

1. 前提是已知 list 中各个元素的值，如此题中用 0, 1, 2代表三种颜色
2. 因为各个元素非常可能重复出现，因此只要知道0, 1, 2分别出现了多少次，就知道结果应该长什么样：假设UnsortedList = [1, 2, 2, 0, 1, 0, 2]，其中有2个0，2个1，3个2；因此，我们知道sort后，最开始会有两个0，紧接着是两个1，最后三个2。直接override原来的list即可

    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        num0, num1, num2 = 0, 0, 0
        for i in nums:
            if i == 0:
                num0 += 1
            if i == 1:
                num1 += 1
            if i == 2:
                num2 += 1
        nums.clear()
        nums += [0 for a in range(num0)]
        nums += [1 for b in range(num1)]
        nums += [2 for c in range(num2)]

result.png