📝 题目描述

题目链接：颜色分类

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

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

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

示例 1：

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

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

解释：

该数组包含两个 0、两个 1 和两个 2。将它们原地排序后，所有 0 排在最前面，接着是所有 1，最后是所有 2。

示例 2：

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

输出：[0,1,2]

解释：

数组中有且仅有一个 0、一个 1 和一个 2，按 0、1、2 的顺序原地排列。

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

💡 解题思路

方法一：计数排序

计数排序，很直观、很容易想到的方法。反正就三个数字“0、1、2”，最后无非就是给这三个数字排序。因此我们可以先扫描一遍数组，统计一下有多少个“0、1、2”，然后按照统计结果，原地将他们写进数组。

方法二：三指针

用三个指针（left、i、right）维护四个区域：

下标范围 含义
[0, left) 已经放好的 0
[left, i) 已经放好的 1
[i, right] 尚未处理的元素
[right + 1, n) 已经放好的 2

这里 [a, b) 表示包含 a，不包含 b。每次只检查未知区域最左端的 nums[i]。

具体操作是，我们初始化 left = 0 表示下一个0应该放的位置，i = 0 表示下一个1该放的位置，right = nums.size() - 1 表示下一个2该放的位置，然后从左往右扫描：

  • 如果 nums[i] == 0，则将 nums[left] 与 nums[i] 交换，然后 left 与 i 都向右移动；
  • 如果 nums[i] == 1，则啥也不用做， i 向右移动；
  • 如果 nums[i] == 2，则将 nums[right] 与 nums[i] 交换，然后 right 向左移动。

需要注意的是，遇到 2 时，不能 ++i（向右移动），因为 right 位置也属于未知区域，交换过来的数可能是 0、1 或 2，必须重新检查。

例如数组 [1, 2, 0]，当 i = 1 时，把 2 和末尾的 0 交换：

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

此时必须继续处理 i 位置的 0。如果直接 ++i，循环就会结束，结果仍然无序。

遇到 0 时，可以 ++i，根据区域定义：

  • 当 left < i 时，nums[left] 一定是已经确认过的 1；交换后，i 位置是 1，可以直接跳过；
  • 当 left == i 时，只是自己和自己交换，这个 0 已经就位，也可以继续前进。

因此，虽然 i 有时不动，这仍然是一趟扫描。 未知区域的长度是 right - i + 1，每轮都会通过 ++i 或 --right 缩小一个位置，因此恰好处理 n 次.

🔧 代码实现

1、计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    void sortColors(vector<int>& nums) {
        // 统计0的数量和1的数量
        int num0 = 0, num1 = 0;
        for (auto& num : nums) {
            if (num == 0) {
                num0++;
            } else if (num == 1) {
                num1++;
            }
            // 不用统计2的数量，剩下的就是2
        }
        // 统计完成后原地写入
        for (int i = 0; i < nums.size(); i++) {
            if (i < num0) {
                nums[i] = 0;
            } else if (i < (num0 + num1)) {
                nums[i] = 1;
            } else {
                nums[i] = 2;
            }
        }
    }
};

2、三指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0;
        int i = 0;
        int right = static_cast<int>(nums.size()) - 1;

        while (i <= right) {
            if (nums[i] == 0) {
                swap(nums[left], nums[i]);
                ++left;
                ++i;
            } else if (nums[i] == 1) {
                ++i;
            } else {
                swap(nums[i], nums[right]);
                --right;
                // 暂时不移动 i，继续检查交换过来的元素
            }
        }
    }
};

📊 复杂度分析

1、计数排序

  • 时间复杂度：O(n)O(n)，先统计，再回填，O(2n)O(2n) 仍然是 O(n)O(n)。
  • 空间复杂度：O(1)O(1)，只用了固定数量的变量，也符合原地修改的要求。

2、三指针

  • 时间复杂度：O(n)O(n)，只需要一趟扫描。
  • 空间复杂度：O(1)O(1)，只用了常数个变量。

🎯 总结

  • 核心思想：技巧类题目，三指针的思路类似于前面的题目“移动零”。