题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意: 不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

我的解法——三指针（AC）

p0记录0分段的最后一个0出现的位置，p1记录1分段的最后一个1出现的位置，p2记录2分段的最后一个2出席那的位置，实时更新这三个指针。
一开始用双指针p0和p2，死活没做出来，边界条件太多，三指针就好多了，虽然步骤繁琐了，但是代码好写很多。
时间复杂度O(n)，空间复杂度O(1)
Beat ？%

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        
        p0 = -1
        p1 = -1
        p2 = -1
        p = 0
        length = len(nums)
        
        while(p < length):
            print(p,p0,p1,p2)
            now = nums[p]
            if(now == 2 or now == 1 or now == 0):
                p2 += 1
            if(now == 1 or now == 0):
                p1 += 1
                nums[p1],nums[p2] = nums[p2],nums[p1]
            if(now == 0):
                p0 += 1
                nums[p1],nums[p0] = nums[p0],nums[p1]
            p += 1

其他解法——三路快排

三路快排！