颜色分类 - Stellar Observer Protocol

642 字

3 分钟

颜色分类

2025-09-02

Algorithms

数组

/

双指针

/

排序

题目描述#

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

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

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

解题思路#

三指针分区：
- 使用 low 指针标记0的右边界
- 使用 high 指针标记2的左边界
- 使用 mid 指针遍历数组
元素分类：
- 遇到0：与low交换，low和mid右移
- 遇到1：mid右移
- 遇到2：与high交换，high左移
单向遍历：
- 只需一次遍历完成排序
原地操作：
- 无需额外存储空间
终止条件：
- 当 mid > high 时完成

关键洞察#

分区思想：
- 将数组划分为0区、1区和2区
边界移动：
- low 保证左侧全为0
- high 保证右侧全为2
交换逻辑：
- 遇到2时 mid 不移动（交换后需重新判断）
遍历效率：
- 每个元素最多被访问两次
荷兰国旗：
- 基于Dijkstra的三色问题解决方案

复杂度分析#

指标	说明
时间复杂度	O(n)：单次遍历数组
空间复杂度	O(1)：原地操作，仅需常数空间
最优情况	O(n)：全0数组仍需完整遍历
最坏情况	O(n)：同上

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @return {void} Do not return anything, modify nums in-place instead.
4
 */
5
var sortColors = function (nums) {
6
    let red = 0, white = 0;
7
    for (const num of nums) {
8
        if (num === 0) red++;
9
        if (num === 1) white++;
10
    }
11
    let i = 0;
12
    while (red) {
13
        nums[i++] = 0;
14
        red--;
15
    }
16
    while (white) {
17
        nums[i++] = 1;
18
        white--;
19
    }
20
    while (i < nums.length) {
21
        nums[i++] = 2;
22
    }
23
};

1
pub fn sort_colors(nums: &mut Vec<i32>) {
2
    let (mut low, mut mid, mut high) = (0, 0, nums.len() - 1);
3

4
    while mid <= high {
5
        match nums[mid] {
6
            0 => {
7
                nums.swap(low, mid);
8
                low += 1;
9
                mid += 1;
10
            }
11
            1 => {
12
                mid += 1;
13
            }
14
            2 => {
15
                nums.swap(mid, high);
16
                if high == 0 { break; } // 防止无符号整数下溢
17
                high -= 1;
18
            }
19
            _ => unreachable!(),
20
        }
21
    }
22
}

1
def sortColors(nums):
2
    low, mid, high = 0, 0, len(nums) - 1
3

4
    while mid <= high:
5
        if nums[mid] == 0:
6
            nums[low], nums[mid] = nums[mid], nums[low]
7
            low += 1
8
            mid += 1
9
        elif nums[mid] == 1:
10
            mid += 1
11
        else:  # nums[mid] == 2
12
            nums[mid], nums[high] = nums[high], nums[mid]
13
            high -= 1