python实现leetcode之75. 颜色分类

解题思路

三路快速排序，假设划分的元素是1
然后保证
[0...red)是0
[red...white)是1
[white...blue]是未检查区
(blue...end-1)是2

75. 颜色分类

代码

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # [0-red-red][red-red-white][white-mix-blue][blue-blue-end]
        red, white, blue = 0, 0, len(nums) - 1
        while white <= blue:
            white = max(white, red)
            if nums[red] == 0:
                red += 1
                white += 1
            elif nums[blue] == 2:
                blue -= 1
            elif nums[white] == 1:
                white += 1
            elif nums[white] == 0:
                nums[red], nums[white] = nums[white], nums[red]
                red += 1
            elif nums[blue] == 0:
                nums[red], nums[blue] = nums[blue], nums[red]
                red += 1
            else:
                nums[white], nums[blue] = nums[blue], nums[white]
                white += 1
                blue -= 1