颜色分类：整理杂乱的红白蓝

大家好！今天我们要探讨一个既直观又充满挑战的问题——颜色分类（Color Sort）。这个问题虽然表面上看起来简单，但它背后隐藏着重要的算法思想，在数组处理、原地算法和荷兰国旗问题中都有特殊地位。让我们一起深入这个问题的本质，探索多种巧妙解法！

🌟 颜色分类：把混乱变成秩序

什么是"颜色分类"？想象你有一堆红白蓝三种颜色的球，现在需要将它们按照红、白、蓝的顺序排列整齐。这个过程就像是整理一面混乱的国旗，让它恢复应有的秩序与美观。

🎯 问题描述：整理三色数组

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

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

注意：不能使用标准库的排序函数来解决这个问题，必须仅使用常数空间的一趟扫描算法。

例如：

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

🚶‍♀️ 解法一：计数排序（简单但并非最优）

最直接的方法是统计数组中0、1、2的个数，然后重新填充数组：

class Solution {
    public void sortColors(int[] nums) {
        // 计数
        int count0 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else if (num == 2) count2++;
        }
        
        // 重新填充数组
        int i = 0;
        while (count0 > 0) {
            nums[i++] = 0;
            count0--;
        }
        while (count1 > 0) {
            nums[i++] = 1;
            count1--;
        }
        while (count2 > 0) {
            nums[i++] = 2;
            count2--;
        }
    }
}

时间复杂度：O(n)，需要遍历数组两次
空间复杂度：O(1)，只使用了常数级别的额外空间

这个解法符合题目要求的常数空间，但它需要两次遍历。我们能做得更好吗？

🏇 解法二：双指针法（更优但不是最佳）

我们可以使用两个指针，分别跟踪应该放置0和1的位置：

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;    // 下一个0应该放置的位置
        int p1 = 0;    // 下一个1应该放置的位置
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                // 交换当前元素与p0位置的元素
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                
                // 如果p0小于p1，说明我们把一个1换到了当前位置
                // 需要再次交换，将1放到正确的位置
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                
                p0++;
                p1++;
            } else if (nums[i] == 1) {
                // 交换当前元素与p1位置的元素
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                
                p1++;
            }
        }
    }
}

时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(1)，只使用了常数额外空间

这个解法虽然只需要一次遍历，但代码相对复杂，不够直观。

🏆 解法三：荷兰国旗问题（最优解）

这个问题实际上是由计算机科学家Edsger W. Dijkstra提出的"荷兰国旗问题"的一个变种。荷兰国旗恰好是由红、白、蓝三色组成的，与我们的问题一致。

解法的核心思想是使用三个指针将数组分成四个区域：

• [0, p0)：全部是0（红色）
• [p0, p1)：全部是1（白色）
• [p1, p2]：待分类区域
• (p2, n-1]：全部是2（蓝色）

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;           // 指向下一个应放0的位置
        int p2 = nums.length - 1; // 指向下一个应放2的位置
        int curr = 0;         // 当前处理的元素
        
        while (curr <= p2) {
            if (nums[curr] == 0) {
                // 遇到0，与p0位置交换，并移动p0和curr
                swap(nums, curr, p0);
                p0++;
                curr++;
            } else if (nums[curr] == 2) {
                // 遇到2，与p2位置交换，并移动p2
                // 注意此时curr不移动，因为交换来的元素还未处理
                swap(nums, curr, p2);
                p2--;
            } else {
                // 遇到1，只移动curr
                curr++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(1)，只使用了常数额外空间

🎭 荷兰国旗算法的直观理解：拔河游戏

想象这样一个场景：有三队人（0队、1队、2队）在玩拔河游戏。0队站在左边，2队站在右边，1队站在中间。游戏开始时，大家都混在一起，现在我们要把他们分开。

我们从左向右检查每个人：

• 如果是0队的，就把他与左边区域的边界交换，然后左边区域向右扩展一步
• 如果是2队的，就把他与右边区域的边界交换，然后右边区域向左扩展一步
• 如果是1队的，就保持原位，继续检查下一个人

最终，0队都在最左边，2队都在最右边，1队自然就在中间了。

🎬 图解荷兰国旗算法

以输入数组 [2,0,2,1,1,0] 为例：

1. 初始状态：p0 = 0, curr = 0, p2 = 5 [2,0,2,1,1,0] ^ ^ p0 p2 curr

2. nums[curr] = 2，交换nums[curr]和nums[p2]，p2-- [0,0,2,1,1,2] ^ ^ p0 p2 curr

3. nums[curr] = 0，交换nums[curr]和nums[p0]，p0++，curr++ [0,0,2,1,1,2] ^ ^ p0 p2 curr

4. nums[curr] = 2，交换nums[curr]和nums[p2]，p2-- [0,0,1,1,2,2] ^ ^ p0 p2 curr

5. nums[curr] = 1，curr++ [0,0,1,1,2,2] ^ ^ p0 p2 curr

6. nums[curr] = 1，curr++ [0,0,1,1,2,2] ^ ^ p0 p2 curr

最终结果为 [0,0,1,1,2,2]，完成排序！

🔍 为什么荷兰国旗算法有效？

荷兰国旗算法的关键在于维护三个指针，分别表示三个颜色的边界。通过不断调整这些边界，我们可以确保：

• 所有0都被移到数组左侧
• 所有2都被移到数组右侧
• 所有1自然就在中间

这个算法只需要一次遍历，而且空间复杂度是O(1)，达到了时间和空间的双重最优。

🌱 扩展思考：如果有更多种颜色？

如果有k种颜色（而不仅仅是3种），我们可能需要回到计数排序的思路，或者使用快速排序的partition思想进行多次划分。

class Solution {
    public void sortColors(int[] nums, int k) {
        // 计数排序思路
        int[] counts = new int[k];
        
        // 统计每种颜色的数量
        for (int num : nums) {
            counts[num]++;
        }
        
        // 重新填充数组
        int index = 0;
        for (int color = 0; color < k; color++) {
            for (int count = 0; count < counts[color]; count++) {
                nums[index++] = color;
            }
        }
    }
}

🌐 实际应用：从排序到分区

颜色分类问题的思想在现实中有广泛应用：

• 数据处理：将数据分成若干类别进行处理
• 图像处理：图像分割和颜色量化
• 内存管理：垃圾收集算法中的对象分类
• 数据库索引：数据分区提高查询效率

💯 解题心得：特殊问题的特殊解法

颜色分类问题展示了一个重要的算法设计思想：针对特定问题的特殊性质设计最优算法。

• 当我们知道数据只有少量几种取值时，可以设计比通用排序更高效的解法
• 有时候，问题可以转化为经典问题（如荷兰国旗问题），利用已有的算法思想
• 指针技巧在数组处理中非常有用，特别是需要原地修改数组时

🎓 面试小贴士

面试中遇到颜色分类问题，建议按以下步骤回答：

1. 先提出计数排序的方法，说明这是最直观的两遍扫描法
2. 然后介绍双指针的方法，表明你在优化第一个解法
3. 最后讲解荷兰国旗算法，展示你对经典算法问题的理解
4. 讨论如何将这个思想应用到其他问题，如快速排序中的三路划分

🤔 思考题

如果数组中有四种颜色（用0,1,2,3表示），如何使用类似荷兰国旗的算法，在一次遍历中完成排序？

---

作者：忍者算法
公众号：忍者算法

颜色分类问题虽然简单，但它是理解分区算法和多指针技巧的绝佳例子。通过这个问题，我们不仅学会了解决特定问题的技巧，还触及了算法设计的一般思路。希望这次探讨能帮助你在数组处理和排序算法方面有更深的理解！

#算法面试 #LeetCode #荷兰国旗问题 #数组排序 #双指针技巧

💪 练习建议

想要巩固对这个问题的理解，不妨尝试：

1. 手动模拟荷兰国旗算法的过程，理解三个指针的移动规律
2. 尝试实现处理四种颜色的分类算法
3. 将这种思想应用到快速排序中，实现三路快排

记住，算法的精髓不在于记忆代码，而在于理解思想。当你能够自然地推导出荷兰国旗算法，你就真正掌握了这个问题背后的核心思想！