75. 颜色分类

题目链接：75. 颜色分类

题目描述

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

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

你必须在不使用库内置的 sort 函数的情况下解决这个问题。且仅使用常数级额外空间的一次遍历算法。

核心思考：三指针（三路划分）的优化实现

这道题是经典的“荷兰国旗问题”（Dutch National Flag Problem）。虽然标准做法是利用两个指针分别代表 0 的边界和 2 的边界进行交换，但本代码采用了一种更为巧妙且简洁的覆盖填补法。

1. 指针定义：
   • p0：指向下一个应当填入 0 的位置。
   • p1：指向下一个应当填入 1 的位置。
2. 逻辑流程：
   • 我们遍历数组，对于每一个当前元素 x，我们先假定它是最末端的颜色 2，即执行 nums[i] = 2。
   • 如果原值 x <= 1：说明这个位置至少应该是 1。我们在当前 p1 的位置填入 1，并将 p1 后移。
   • 如果原值 x == 0：说明这个位置必须是 0。我们在当前 p0 的位置填入 0，并将 p0 后移。
3. 关键点：
   这种填补方式精妙地利用了指针的领先关系：由于 0 的位置一定在 1 的位置之前（或重合），当我们在 p0 处填入 0 时，实际上会覆盖掉在该位置之前刚刚填入的 1 副本。因此，通过这种多级覆盖，最终能形成 0...1...2... 的有序排列。

解题思路 (Python)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # p0 和 p1 分别维护 0 和 1 的写入边界
        p0 = p1 = 0
        for i, x in enumerate(nums):
            # 将当前位置默认设为 2
            nums[i] = 2
            
            # 如果原数值小于等于 1，说明需要写入 1
            if x <= 1:
                nums[p1] = 1
                p1 += 1
            
            # 如果原数值等于 0，说明需要写入 0
            # 注意：如果此处触发，会覆盖掉上面刚刚写在 p0 位置的 1，形成正确的顺序
            if x == 0:
                nums[p0] = 0
                p0 += 1

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组的长度。我们通过三指针逻辑在一次遍历内完成了所有数值的重新定位。
• 空间复杂度：$O(1)$，仅使用了常数个指针变量进行索引管理。