LeetCode 75：颜色分类 | 荷兰国旗问题的多种解法

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 0two n-1cur 00 区索引 [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)是解决这类问题的最优方法。