# 75. 颜色分类

# 题目描述

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

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

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

示例 1：

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

1
2

示例 2：

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

1
2

提示：

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

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗?

# 思路

这道题也叫"荷兰国旗问题"(Dutch National Flag Problem),是经典的数组分类问题。

# 方法一:计数排序(两趟扫描)

最简单的思路:统计 0、1、2 各有多少个,然后按顺序填回数组。

第一趟:统计 cnt0、cnt1、cnt2
第二趟:先填 cnt0 个 0,再填 cnt1 个 1,最后填 cnt2 个 2

1
2

时间复杂度 O(n),空间复杂度 O(1),但需要两趟扫描。

# 方法二:双指针(一趟扫描,最优解)

进阶要求是一趟扫描,这就需要用到双指针思想。

核心思路:用两个指针 p0 和 p2 分别指向"下一个 0 应该放的位置"和"下一个 2 应该放的位置"。

具体做法:

p0 初始化为 0,指向数组开头(0 应该放在前面)
p2 初始化为 n-1,指向数组末尾(2 应该放在后面)
用指针 i 从左到右遍历

遍历时:

如果 nums[i] == 0:和 nums[p0] 交换,p0++,i++
如果 nums[i] == 2:和 nums[p2] 交换,p2--,i 不动(因为交换过来的数还没检查)
如果 nums[i] == 1:i++(1 就放在中间,不用管)

为什么遇到 2 时 i 不动?

因为从 p2 位置交换过来的数可能是 0、1、2 中的任何一个,还需要再判断一次。但从 p0 交换过来的数,一定是 1 或已经处理过的,所以可以直接 i++。

这样一趟遍历下来:

[0, p0) 区间全是 0
[p0, i) 区间全是 1
(p2, n-1] 区间全是 2

# 模拟过程

以 nums = [2,0,2,1,1,0] 为例:

初始状态:

nums:  [2, 0, 2, 1, 1, 0]
        ↑              ↑
        i              p2
        p0

1
2
3
4

p0 = 0
p2 = 5
i = 0

第 1 步: nums[0] = 2,交换 nums[0] 和 nums[5]

交换后: [0, 0, 2, 1, 1, 2]
         ↑           ↑
         i           p2
         p0

1
2
3
4

p2 = 4
i = 0(不动)

第 2 步: nums[0] = 0,交换 nums[0] 和 nums[0](自己和自己)

nums:   [0, 0, 2, 1, 1, 2]
            ↑        ↑
            i        p2
            p0

1
2
3
4

p0 = 1
i = 1

第 3 步: nums[1] = 0,交换 nums[1] 和 nums[1](自己和自己)

nums:   [0, 0, 2, 1, 1, 2]
               ↑     ↑
               i     p2
               p0

1
2
3
4

p0 = 2
i = 2

第 4 步: nums[2] = 2,交换 nums[2] 和 nums[4]

交换后: [0, 0, 1, 1, 2, 2]
               ↑  ↑
               i  p2
               p0

1
2
3
4

p2 = 3
i = 2(不动)

第 5 步: nums[2] = 1,i++

nums:   [0, 0, 1, 1, 2, 2]
                  ↑↑
                  ip2
                  p0

1
2
3
4

i = 3

第 6 步: nums[3] = 1,i++

nums:   [0, 0, 1, 1, 2, 2]
                     ↑
                     i (i > p2,结束)

1
2
3

i = 4 > p2,遍历结束

最终结果: [0, 0, 1, 1, 2, 2]

drawio 提示词: 画两张图展示双指针交换过程。第一张展示初始状态和指针含义,用不同颜色标注三个区域:[0,p0) 是 0 区、[p0,i) 是 1 区、(p2,n-1] 是 2 区,中间 [i,p2] 是未处理区。第二张展示关键的几步交换,选取遇到 2 时的交换(i 不动)和遇到 0 时的交换(i 移动),用箭头表示指针移动和元素交换,最终展示三个区域完全分离。两张图画布统一,Logo 放左下角。

文件名:

0075.sort-colors-01-pointers-regions.drawio
0075.sort-colors-02-swap-process.drawio

# 解题代码

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0 = 0; // 下一个 0 应该放的位置
        int p2 = nums.size() - 1; // 下一个 2 应该放的位置
        int i = 0;
        
        while (i <= p2) {
            if (nums[i] == 0) {
                swap(nums[i], nums[p0]);
                p0++;
                i++; // 从 p0 交换过来的一定是 1 或已处理的,可以直接 i++
            } else if (nums[i] == 2) {
                swap(nums[i], nums[p2]);
                p2--;
                // i 不动,因为从 p2 交换过来的数还没检查
            } else { // nums[i] == 1
                i++; // 1 放在中间,不用管
            }
        }
    }
};

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

# 复杂度分析

时间复杂度:O(n),一趟扫描
空间复杂度:O(1),原地交换

# 其他语言

# Python3

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0 = 0
        p2 = len(nums) - 1
        i = 0
        
        while i <= p2:
            if nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                p0 += 1
                i += 1
            elif nums[i] == 2:
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
                # i 不动
            else:  # nums[i] == 1
                i += 1

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

# Java

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p2 = nums.length - 1;
        int i = 0;
        
        while (i <= p2) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                p0++;
                i++;
            } else if (nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                p2--;
            } else {
                i++;
            }
        }
    }
}

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

# Go

func sortColors(nums []int) {
    p0 := 0
    p2 := len(nums) - 1
    i := 0
    
    for i <= p2 {
        if nums[i] == 0 {
            nums[i], nums[p0] = nums[p0], nums[i]
            p0++
            i++
        } else if nums[i] == 2 {
            nums[i], nums[p2] = nums[p2], nums[i]
            p2--
        } else {
            i++
        }
    }
}

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

# JavaScript

var sortColors = function(nums) {
    let p0 = 0;
    let p2 = nums.length - 1;
    let i = 0;
    
    while (i <= p2) {
        if (nums[i] === 0) {
            [nums[i], nums[p0]] = [nums[p0], nums[i]];
            p0++;
            i++;
        } else if (nums[i] === 2) {
            [nums[i], nums[p2]] = [nums[p2], nums[i]];
            p2--;
        } else {
            i++;
        }
    }
};

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

# 与代码随想录联系

这道题是双指针技巧的经典应用,体现了"分区"的思想。

类似的思想在快速排序的 partition 过程中也会用到:选一个基准值,把小于基准的放左边,大于基准的放右边。

本题是三路快排(3-way QuickSort)的简化版:把数组分成三个区域,小于、等于、大于某个值。

如果录友们对双指针还不熟悉,可以看代码随想录的双指针章节,里面有很多经典的双指针题目:

27. 移除元素 — 快慢指针
283. 移动零 — 类似的分区思想
15. 三数之和 — 对撞指针

双指针的核心是"维护区间不变性":在本题中,我们始终维护 [0,p0) 全是 0,(p2,n-1] 全是 2,这样遍历结束时,数组自然就排好序了。

这种思想在很多原地修改数组的题目中都会用到,非常重要!

验证登录状态...

# 75. 颜色分类

# 题目描述

# 思路

# 方法一:计数排序(两趟扫描)

# 方法二:双指针(一趟扫描,最优解)

# 模拟过程

# 解题代码

# 复杂度分析

# 其他语言

# Python3

# Java

# Go

# JavaScript

# 与代码随想录联系

评论