75.颜色分类

原题地址

这题是典型的荷兰国旗问题，最初由 Edsger W. Dijkstra提出。

三路快排 ：与双路快排的不同是，它每次挑选出枢纽元素后，不是将数组分为小于等于枢纽元素，大于枢纽元素两部分，而是分成小于枢纽元素，等于枢纽元素，大于枢纽元素三部分，然后再对大于枢纽元素和小于枢纽元素这两个子序列进行上述操作。
三路快排代码

这里借助三路快排的思路，一次遍历就可以将荷兰国旗问题解决。

思路

我们定义三个区间[0, p0), [p0, p2], (p2, n-1]，表示排序后0,1,2的三个区间。

所以p0表示0的右边界，p2表示2的左边界，我们再定义cur表示当前元素

遍历步骤如下：

1. nums[cur]==0，则swap(nums[cur],nums[p0])，同时cur++;p0++
2. nums[cur]==1，则直接cur++
3. nums[cur]==2，则swap(nums[cur],nums[p2])，同时只有p2--

很好理解，就是当前元素是0，就把它放到左边0的区间中，同时0的区间右端点更新；当前元素是1，直接省略掉；当前元素时2，就把它放到右边的2的区间中，同时区间左端点更新。

可是，为什么当前元素是0，cur和p0都要更新；但当前元素是2，则只有p2更新呢？

这个是由于当前元素是0时，不管是nums[cur], 还是nums[p0]，都检查过了；但是当前元素是2时，nums[p2]是还没有进行检查的元素，如果交换后cur++，就把该元素忽略掉了。

不理解的话自己可以手推一个例子看一下

Python代码

def sortColors(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    p0, p2, cur = 0, len(nums)-1, 0
    while cur <= p2:
        if nums[cur] == 0:
            nums[cur], nums[p0] = nums[p0], nums[cur]
            p0 += 1
            cur += 1
        elif nums[cur] == 2:
            nums[cur], nums[p2] = nums[p2], nums[cur]
            p2 -= 1
        else:
            cur += 1

这个题用常规快排也可以解决，只不过需要遍历两次，不过时间复杂度也是O(n)

def sortColors(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    def Partition(low, high, pivlot):
        temp = nums[low]
        while low < high:
            while low < high and nums[high] > pivlot:
                high -= 1
            nums[low] = nums[high]
            while low < high and nums[low] <= pivlot:
                low += 1
            nums[high] = nums[low]
        nums[low] = temp
    # 使用快排的思路，两遍即可
    # 第一遍，排好0，第二遍，排好1，时间复杂度为O(2*n)=O(n)
    # 第一遍，排好0
    l, h = 0, len(nums)-1
    while l <= h and nums[l] == 0:
        l += 1
    if l < h:
        Partition(l, h, 0)
    # 第二遍，排好1
    l = 0
    while l <= h and nums[l] <= 1:
        l += 1
    if l < h:
        Partition(l, h, 1)

时间复杂度O(n)

空间复杂度O(1)