LeetCode 75：颜色分类 | 荷兰国旗问题的多种解法
引言
颜色分类（Sort Colors）是 LeetCode 第 75 题，难度为 Medium。题目要求将包含 0、1、2 三种值的数组排序，使所有 0 在前面，所有 1 在中间，所有 2 在后面。这道题也被称为荷兰国旗问题，是三路分区的经典案例。
这道题有多种解法：计数排序 O(n) 两趟、原地交换 O(n) 一趟。本文将详细介绍这两种解法及其优化。
问题分析
题目描述
给定一个数组 nums，元素只有 0、1、2 三种值，原地排序使数组变为有序。例如，输入 [2,0,2,1,1,0]，输出 [0,0,1,1,2,2]。
问题特点
这道题的核心挑战在于如何在一趟遍历中完成排序。传统的排序算法（如快速排序）可以解决这个问题，但需要 O(n log n) 时间。荷兰国旗问题要求 O(n) 时间和 O(1) 空间。
解法一：计数排序
算法原理
计数排序是一种简单的解法。首先统计 0、1、2 的数量，然后重写数组。
def sortColors_counting(nums): count = [0, 0, 0] for num in nums: count[num] += 1 index = 0 for i in range(3): for _ in range(count[i]): nums[index] = i index += 1复杂度分析
时间复杂度：O(n)，两趟遍历
空间复杂度：O(1)
解法二：三路分区（单趟）
算法原理
使用三个指针：zero 指向 0 区的右边界，two 指向 2 区的左边界，cur 指向当前遍历位置。
def sortColors_three_way(nums): zero = 0 two = len(nums) - 1 cur = 0 while cur <= two: if nums[cur] == 0: nums[zero], nums[cur] = nums[cur], nums[zero] zero += 1 cur += 1 elif nums[cur] == 2: nums[two], nums[cur] = nums[cur], nums[two] two -= 1 else: cur += 1算法详解
初始状态：zero = 0，two = n-1，cur = 0
- 0 区：索引 [0, zero)
- 未排序区：[cur, two]
- 2 区：(two, n-1]
当 nums[cur] == 0 时，与 zero 位置交换，zero 和 cur 都右移。
当 nums[cur] == 2 时，与 two 位置交换，two 左移（cur 不变，因为交换过来的元素还没检查）。
当 nums[cur] == 1 时，cur 右移。
复杂度分析
时间复杂度
时间复杂度为 O(n)，因为 cur 最多移动 n 次，zero 和 two 也最多移动 n 次。
空间复杂度
空间复杂度为 O(1)，只使用了三个指针变量。
代码实现
Python 实现
def sortColors(nums): zero = 0 two = len(nums) - 1 cur = 0 while cur <= two: if nums[cur] == 0: nums[zero], nums[cur] = nums[cur], nums[zero] zero += 1 cur += 1 elif nums[cur] == 2: nums[two], nums[cur] = nums[cur], nums[two] two -= 1 else: cur += 1Java 实现
public void sortColors(int[] nums) { int zero = 0; int two = nums.length - 1; int cur = 0; while (cur <= two) { if (nums[cur] == 0) { swap(nums, zero, cur); zero++; cur++; } else if (nums[cur] == 2) { swap(nums, two, cur); two--; } else { cur++; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }边界情况处理
空数组
当数组为空时，循环不会执行，直接返回。
全相同元素
当所有元素都相同时，如 [1, 1, 1]，算法会正确处理：cur 会一直右移到 two 位置，然后结束。
测试用例
def test_sort_colors(): nums1 = [2, 0, 2, 1, 1, 0] sortColors(nums1) assert nums1 == [0, 0, 1, 1, 2, 2] nums2 = [2, 0, 1] sortColors(nums2) assert nums2 == [0, 1, 2] nums3 = [0] sortColors(nums3) assert nums3 == [0] nums4 = [1, 1, 1] sortColors(nums4) assert nums4 == [1, 1, 1] print("所有测试用例通过！")总结
颜色分类问题展示了荷兰国旗问题的标准解法。三路分区方法只需要一趟遍历就将数组排序，时间复杂度 O(n)，空间复杂度 O(1)，是解决这类问题的最优方法。
