LeetCode 75. 颜色分类 题目描述 给定一个包含红色、白色和蓝色元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，且按照红色（0）、白色（1）、蓝色（2）的顺序排列。 你不能使用库的排序函数来解决这个问题。 示例： 输入：nums = [ 2,0,2,1,1,0 ] 输出：[ 0,0,1,1,2,2 ] 解题思路分析 这个题目本质是 数组分区 问题，要求将数组按三个类别（0、1、2）重新排列。 一种直接的思路是使用计数排序：先统计0、1、2的数量，然后重写数组。但题目希望我们尝试一次遍历完成。 我们可以使用 三指针（荷兰国旗问题） 的方法，在单次遍历中完成分区。 详细步骤讲解 初始化三个指针 low ：指向下一个0应该放置的位置，初始为0。 high ：指向下一个2应该放置的位置，初始为 n-1 （数组末尾）。 current ：当前遍历的指针，初始为0。 遍历规则 当 current <= high 时（注意是 high 而不是数组末尾，因为 high 后面的元素已经是2了），根据 nums[current] 的值处理： 如果值为0 ：交换 nums[low] 和 nums[current] ，然后 low 和 current 都向后移动一位。因为交换到 current 位置的元素（来自 low 位置）只能是0或1（原因看后面），所以 current 可以放心前进。 如果值为1 ：不需要交换，直接 current++ 。 如果值为2 ：交换 nums[current] 和 nums[high] ，然后 high-- 。注意此时 current 不前进 ，因为交换过来的元素（原 nums[high] ）可能是0、1或2，还需要检查。 为什么这样做正确？ [0, low-1] 区间内全是0。 [low, current-1] 区间内全是1（因为0已经被交换到前面，2被交换到后面，剩下的就是1）。 [high+1, n-1] 区间内全是2。 current 指针从左向右扫描， high 指针从右向左移动，确保每个元素都被正确处理。 举例说明 初始：nums = [ 2,0,2,1,1,0 ], low=0, current=0, high=5 current=0, nums[ 0]=2 → 交换nums[ 0]和nums[ 5] → [ 0,0,2,1,1,2 ], high=4, current仍为0。 current=0, nums[ 0]=0 → 交换nums[ 0]和nums[ 0]（自身）→ [ 0,0,2,1,1,2 ], low=1, current=1。 current=1, nums[ 1]=0 → 交换nums[ 1]和nums[ 1] → [ 0,0,2,1,1,2 ], low=2, current=2。 current=2, nums[ 2]=2 → 交换nums[ 2]和nums[ 4] → [ 0,0,1,1,2,2 ], high=3, current仍为2。 current=2, nums[ 2 ]=1 → 不交换，current=3。 current=3, nums[ 3 ]=1 → 不交换，current=4。 此时current=4 > high=3，循环结束。数组已排序为[ 0,0,1,1,2,2 ]。 总结 这个方法的关键是利用三个指针将数组分为四个区域，并在一次遍历中通过交换将元素归位到正确区域，时间复杂度O(n)，空间复杂度O(1)，且符合题目“原地”修改的要求。