企业官网建设流程全解析

1. 问题背景与题目解析

这道题目来自力扣（LeetCode）的HOT100系列，编号T.75，题目名为"颜色分类"。题目要求我们将一个包含红色、白色和蓝色元素的数组进行原地排序，使得相同颜色的元素相邻，且按照红色、白色、蓝色的顺序排列。在本题中，我们使用整数0、1和2分别表示红色、白色和蓝色。

这道题看似简单，但它实际上是荷兰国旗问题的一个经典实例，也是快速排序算法中partition过程的一个特例。理解这个问题的解法对于掌握快速排序的核心思想非常有帮助。

注意：题目要求必须在不使用库的sort函数的情况下完成原地排序，这意味着我们需要手动实现排序逻辑。

2. 快速排序与三指针法

2.1 快速排序基础

快速排序的核心思想是分治法，通过选择一个"基准"元素将数组分成两部分，一部分小于基准，一部分大于基准，然后递归地对这两部分进行排序。在标准的快速排序中，partition过程通常使用双指针法：

1. 选择一个基准元素（通常是最后一个元素）
2. 初始化一个指针i表示小于基准的区域的边界
3. 遍历数组，将小于基准的元素交换到i的位置，并递增i
4. 最后将基准元素放到正确的位置

2.2 三指针法适应本题

对于颜色分类问题，我们需要将数组分成三个部分（0、1、2），因此标准的双指针partition需要扩展为三指针法：

• left指针：指向当前0元素应该插入的位置
• right指针：指向当前2元素应该插入的位置
• current指针：用于遍历数组

算法流程：

1. 初始化left=0, right=n-1, current=0
2. 当current <= right时循环： a. 如果nums[current] == 0，交换nums[current]和nums[left]，left++, current++ b. 如果nums[current] == 1，current++ c. 如果nums[current] == 2，交换nums[current]和nums[right]，right--（注意不增加current）

3. 算法实现与代码解析

3.1 Java实现

class Solution { public void sortColors(int[] nums) { int left = 0, right = nums.length - 1; int current = 0; while (current <= right) { if (nums[current] == 0) { swap(nums, current, left); left++; current++; } else if (nums[current] == 1) { current++; } else { swap(nums, current, right); right--; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

3.2 代码解析

1. 初始化三个指针：

   • left始终指向下一个0应该放置的位置
   • right始终指向下一个2应该放置的位置
   • current用于遍历数组

2. 当current遇到0时：

   • 将current位置的0交换到left位置
   • 因为left位置之前已经处理过，所以可以安全地递增left和current

3. 当current遇到1时：

   • 不做交换，直接跳过（1应该在中间区域）
   • 只递增current指针

4. 当current遇到2时：

   • 将current位置的2交换到right位置
   • 由于从right位置交换过来的元素可能是0或1，所以不能递增current，需要在下一次循环中重新检查

关键点：当交换2时不能增加current指针，因为从right位置交换过来的元素可能还需要处理。

4. 算法复杂度分析

4.1 时间复杂度

该算法只需要一次遍历数组，每个元素最多被访问两次（当交换2时可能被重新检查），因此时间复杂度是O(n)，其中n是数组的长度。

4.2 空间复杂度

算法只使用了常数个额外空间（几个指针变量），因此空间复杂度是O(1)，满足题目要求的原地排序条件。

5. 边界条件与测试用例

5.1 常见测试用例

1. 基本用例：

   • 输入：[2,0,2,1,1,0]
   • 输出：[0,0,1,1,2,2]

2. 已排序数组：

   • 输入：[0,0,1,1,2,2]
   • 输出：[0,0,1,1,2,2]

3. 逆序数组：

   • 输入：[2,2,1,1,0,0]
   • 输出：[0,0,1,1,2,2]

4. 全0数组：

   • 输入：[0,0,0]
   • 输出：[0,0,0]

5. 全1数组：

   • 输入：[1,1,1]
   • 输出：[1,1,1]

6. 全2数组：

   • 输入：[2,2,2]
   • 输出：[2,2,2]

7. 空数组：

   • 输入：[]
   • 输出：[]

5.2 特殊边界情况

1. 单元素数组：

   • 输入：[1]
   • 输出：[1]

2. 只有0和1：

   • 输入：[1,0,1,0]
   • 输出：[0,0,1,1]

3. 只有1和2：

   • 输入：[1,2,2,1]
   • 输出：[1,1,2,2]

4. 只有0和2：

   • 输入：[2,0,0,2]
   • 输出：[0,0,2,2]

6. 常见错误与调试技巧

6.1 常见实现错误

1. 交换2后增加current指针：

   • 错误：可能导致未被检查的元素被跳过
   • 正确：交换2后不应增加current，因为从right交换过来的元素可能还需要处理

2. 循环条件错误：

   • 错误：使用current < nums.length作为循环条件
   • 正确：应该是current <= right，因为right之后的元素已经处理过

3. 指针越界：

   • 错误：未检查数组为空的情况
   • 正确：应首先检查数组长度是否为0

6.2 调试技巧

1. 打印中间状态：

   • 在每次交换后打印数组和指针位置，帮助理解算法执行过程

2. 使用小测试用例：

   • 从最小可能的输入开始测试（如[2,0,1]），逐步增加复杂度

3. 边界测试：

   • 特别注意全0、全1、全2的数组，以及空数组和单元素数组

7. 算法优化与变种

7.1 计数排序法

虽然三指针法是最优解，但也可以使用计数排序的思路：

1. 统计0、1、2的个数
2. 按照统计结果重写数组

这种方法需要两次遍历，虽然时间复杂度也是O(n)，但不如三指针法优雅。

7.2 多颜色分类问题

如果颜色种类不止三种（比如k种），可以考虑：

1. 使用k-1次partition将数组分成k部分
2. 或者使用计数排序

7.3 快速排序的partition优化

理解本题的三指针法可以帮助优化快速排序的partition过程，特别是当数组中存在大量重复元素时。

8. 实际应用场景

颜色分类问题虽然简单，但其解法在实际中有广泛应用：

1. 快速排序优化：处理大量重复元素的数组
2. 数据分类：将数据分成几个类别进行处理
3. 图像处理：像素值分类
4. 系统设计：任务优先级调度

9. 力扣HOT100打卡建议

这道题作为HOT100系列的第14题，是算法学习中的一个重要里程碑。以下是一些打卡建议：

1. 理解优先：不要满足于AC，要真正理解三指针法的原理
2. 举一反三：思考如何将这种方法应用到其他分区问题上
3. 多种实现：尝试用不同语言实现该算法
4. 复杂度分析：养成分析时间/空间复杂度的习惯
5. 测试驱动：编写自己的测试用例验证算法正确性

我在实际刷题中发现，真正掌握这道题后，对快速排序和各种分区问题的理解会有质的提升。建议在AC后，可以尝试解决类似的partition问题，如移动零、按奇偶排序数组等，巩固这种解题思路。