LeetCode 75：颜色分类（Sort Colors）题解

Sort Colors 是 LeetCode Hot 100 里面一道非常经典的数组题。

这道题表面上是在“排序”，但它和一般的排序题又不太一样。因为数组中并不是任意整数，而是只会出现三种数字：

• 0

• 1

• 2

题目把它们分别看成：

• 红色

• 白色

• 蓝色

要求你原地对数组进行排序，使得相同颜色的元素相邻，并按照红、白、蓝的顺序排列。

你给出的这份 Java 代码，使用的是这道题非常容易理解的一种做法：

计数排序

这种写法的核心思路非常直接：

1. 先统计 0、1、2 分别出现了多少次

2. 再按数量把数组重写一遍

虽然这题还有一个更经典的进阶解法叫“荷兰国旗问题”，可以在一次遍历中完成排序，但从理解角度来说，你现在这份计数写法其实特别适合作为博客主解法来讲，因为它简单、清晰，而且很容易让读者一下子看懂。

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给定一个包含红色、白色和蓝色，一共 n 个元素的数组 nums，要求你 原地 对它们进行排序，使得相同颜色的元素相邻，并且顺序为：

红色（0） -> 白色（1） -> 蓝色（2）

题目中使用数字来表示颜色：

• 0 表示红色

• 1 表示白色

• 2 表示蓝色

例如：

nums = [2,0,2,1,1,0]

排序后应该变成：

[0,0,1,1,2,2]

这道题的关键点在于：

• 数组中只有三种取值

• 要求原地修改

• 不能直接调用库函数排序

示例

示例 1

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

因为数组中：

• 0 有两个

• 1 有两个

• 2 有两个

所以重新排列后就是：

[0,0,1,1,2,2]

示例 2

输入：nums = [2,0,1]
输出：[0,1,2]

三个颜色各有一个，按顺序排好即可。

最直接的想法是什么？

如果不看题目的特殊结构，很多人第一反应可能是：

• 直接排序

• 或者自己写一个快排 / 归并排序

当然，这样也能把数组排好，但会显得有点“大材小用”。

因为这道题和普通排序题最大的不同在于：

数组中的元素只可能是 0、1、2 三种值。

既然取值范围这么小，我们其实完全没必要使用复杂排序。 更自然的思路应该是：

• 统计三种数字各出现几次

• 然后按照数量把它们重新填回数组

这就是计数排序思想。

核心思路：计数排序

你这份代码的核心可以概括成两步：

第一步：统计频率

先遍历数组，记录：

• 0 出现多少次

• 1 出现多少次

• 2 出现多少次

第二步：重写数组

根据统计结果，把数组改写成：

• 前 cnt[0] 个位置全部放 0

• 接下来 cnt[1] 个位置全部放 1

• 最后 cnt[2] 个位置全部放 2

这样就完成了排序。

由于题目中元素取值范围非常小，这种做法既简单又高效。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    public void sortColors(int[] nums) {
        // cnt[0] 统计 0 的个数
        // cnt[1] 统计 1 的个数
        // cnt[2] 统计 2 的个数
        int[] cnt = new int[3];
​
        // 第一次遍历：统计每种颜色出现次数
        for (int num : nums) cnt[num]++;
​
        // 第二次遍历：按照计数结果重写数组
        for (int i = 0; i < cnt[0]; i++) nums[i] = 0;
​
        for (int i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;
​
        for (int i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;
    }
}

代码拆解

这段代码非常短，但它把“计数排序”的思想体现得很完整。 下面一步一步来看。

1. 为什么可以直接开一个大小为 3 的计数数组？

int[] cnt = new int[3];

因为题目已经保证，数组中的元素只会是：

• 0

• 1

• 2

所以我们只需要一个长度为 3 的数组，就可以把三种数字的出现次数全部记录下来：

• cnt[0] 表示 0 的数量

• cnt[1] 表示 1 的数量

• cnt[2] 表示 2 的数量

这一步的本质是：

把值域很小的排序问题，转化成频率统计问题。

2. 为什么 cnt[num]++ 就能统计频率？

for (int num : nums) cnt[num]++;

因为 num 的值只会是 0、1、2，所以它可以直接作为下标使用。

例如：

• 如果当前元素是 0，就执行 cnt[0]++

• 如果当前元素是 1，就执行 cnt[1]++

• 如果当前元素是 2，就执行 cnt[2]++

假设数组是：

[2,0,2,1,1,0]

遍历结束后，cnt 的值就是：

cnt[0] = 2
cnt[1] = 2
cnt[2] = 2

这就表示三种颜色各出现了两次。

3. 为什么统计完之后可以直接重写数组？

因为排序的最终目标只是让数组变成：

所有 0 在前
所有 1 在中间
所有 2 在后

而一旦我们已经知道：

• 0 有多少个

• 1 有多少个

• 2 有多少个

那么数组的最终形态其实已经完全确定了。

例如：

cnt[0] = 2
cnt[1] = 3
cnt[2] = 1

那么结果一定是：

[0,0,1,1,1,2]

所以根本不需要再比较元素大小，直接按数量把数组写出来就可以了。

4. 为什么第一段循环写成这样？

for (int i = 0; i < cnt[0]; i++) nums[i] = 0;

因为前 cnt[0] 个位置都应该放 0。

例如如果 cnt[0] = 2，那么：

• nums[0] = 0

• nums[1] = 0

这样数组最前面就填好了所有红色。

5. 为什么第二段循环从 cnt[0] 开始？

for (int i = cnt[0]; i < cnt[0] + cnt[1]; i++) nums[i] = 1;

因为前面已经有 cnt[0] 个位置被 0 占掉了。 所以 1 的起始位置自然应该从：

cnt[0]

开始。

而 1 一共要写 cnt[1] 次，所以结束位置是：

cnt[0] + cnt[1] - 1

循环条件写成：

i < cnt[0] + cnt[1]

刚好覆盖这一段区间。

6. 为什么第三段循环从 cnt[0] + cnt[1] 开始？

for (int i = cnt[0] + cnt[1]; i < cnt[0] + cnt[1] + cnt[2]; i++) nums[i] = 2;

同理：

• 前面 cnt[0] 个位置是 0

• 中间 cnt[1] 个位置是 1

所以剩下的位置自然都应该填成 2。

而 2 的起始位置就是：

cnt[0] + cnt[1]

这也说明数组最终被分成了连续三段：

[0 .... 0][1 .... 1][2 .... 2]

手动模拟一遍

我们用经典例子来走一遍：

nums = [2,0,2,1,1,0]

第一步：统计次数

初始化：

cnt = [0,0,0]

遍历后得到：

• 0 出现 2 次

• 1 出现 2 次

• 2 出现 2 次

所以：

cnt = [2,2,2]

第二步：重写数组

先写 0：

nums[0] = 0
nums[1] = 0

数组变成：

[0,0,2,1,1,0]

再写 1：

nums[2] = 1
nums[3] = 1

数组变成：

[0,0,1,1,1,0]

最后写 2：

nums[4] = 2
nums[5] = 2

最终数组变成：

[0,0,1,1,2,2]

排序完成。

为什么这个方法是正确的？

因为这道题的数组元素只有三种值。 而“排序”对于这种特殊数组来说，其实并不需要真的比较元素大小，只需要保证：

• 所有 0 放在最前面

• 所有 1 放在中间

• 所有 2 放在最后面

一旦统计出这三种值各自的数量，数组最终的排列顺序就被唯一确定了。

因此：

• 统计阶段不会漏掉任何元素

• 重写阶段也不会多写或少写任何元素

• 最终结果一定满足题目要求

所以这个算法是完全正确的。

复杂度分析

时间复杂度

代码分成两次线性遍历：

1. 第一次遍历统计频率

2. 第二次遍历重写数组

因此总时间复杂度是：

O(n)

空间复杂度

额外只用了一个长度为 3 的数组 cnt：

O(1)

因为这个空间大小和输入规模 n 无关，是常数级。

这道题真正想考什么？

这道题表面上看是排序题，但本质上考察的是：

第一，能不能利用题目的特殊条件

很多人一看到“排序”就习惯性地想快排、归并排序。 但这道题中的值域只有 0、1、2 三种，所以最关键的并不是套通用排序模板，而是：

看出这是一个很适合计数的问题。

第二，是否理解“值域小”时可以考虑计数排序

计数排序并不是所有排序题都能用，但当数据范围很小、而且值域固定时，它往往会是非常高效的思路。

这也是这道题很值得掌握的一点。

这题为什么还经常提“荷兰国旗问题”？

因为这道题的官方进阶要求通常是：

• 只扫描一遍

• 使用常数空间

• 原地完成排序

而最经典的满足方式就是：

三指针 / 荷兰国旗问题

它的思路是：

• 用一个指针维护 0 区域

• 用一个指针维护 2 区域

• 当前指针扫描数组并交换元素

• 最终在一次遍历中完成分类

这个解法更“高级”，也是面试中更常被追问的版本。

不过从博客写作角度来说，你现在这份计数排序代码作为基础解法非常合适。 因为它更容易让读者先把题意和结构理解透。 等基础版本讲清楚后，再补一句“本题还有一个进阶的三指针做法”，会更完整。

和普通排序题有什么区别？

普通排序题通常面对的是：

• 任意整数

• 比较关系复杂

• 值域很大

而这道题非常特殊：

• 只有 0、1、2 三种值

• 值域极小

• 排序目标其实就是“分类”

所以它本质上更像一道“分类整理”题，而不是真正意义上的复杂排序题。

这也是为什么计数思路会比通用排序更自然。

总结

这道题的核心思想可以概括成一句话：

由于数组中只包含 0、1、2 三种值，所以可以先统计三种数字的出现次数，再按数量把数组重写成 0、1、2 三段。

具体步骤就是：

1. 开一个长度为 3 的计数数组

2. 遍历原数组，统计 0、1、2 的个数

3. 前 cnt[0] 个位置写 0

4. 接下来 cnt[1] 个位置写 1

5. 最后 cnt[2] 个位置写 2

这样就能在：

O(n)

的时间复杂度和：

O(1)

的空间复杂度下完成排序。

这是一道非常经典、也非常值得理解的数组题。 因为它会让你真正体会到：

• 做题时不要只盯着题目表面

• 关键是抓住数据的特殊结构

• 当值域很小的时候，计数往往比比较排序更自然

把这道题真正吃透之后，再去看：

• 前 K 个高频元素

• 数组中重复元素处理

• 桶排序 / 计数排序

• 荷兰国旗问题

这些题时，你会更容易意识到： 很多题不一定要靠“复杂算法”，有时候一个非常贴合数据特征的简单方法，反而就是最好的解法。