[数据结构与算法]颜色分类python(leetcode)

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

- 解法一

思路： 哈希计数，拷贝回去。

代码如下:

class Solution:
    def sortColors(self, nums):
        countEle = {i: 0 for i in nums}
        for i in nums:
            countEle[i] += 1
        tmp = []
        for i in (0, 1, 2):
            tmp += [i] * countEle[i]
        return tmp

解法二

经典的荷兰国旗问题,把一个数组分成三部分.
代码如下:

class Solution:
    def sortColors(self, nums):
        start = index = 0
        end = len(nums) - 1
        while index <= end:
            if nums[index] == 0:
                nums[index], nums[start] = nums[start], nums[index]
                index += 1
                start += 1
            elif nums[index] == 1:
                index += 1
            else:
                nums[index], nums[end] = nums[end], nums[index]
                end -= 1
        return nums