颜色分类

七崽爱吃小饼干2026/02/10阅读 0

颜色分类

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

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

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

示例 1：

codeType

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

示例 2：

codeType

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

提示：

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

解法

解法一：单指针

/**
 Do not return anything, modify nums in-place instead.
 */
function sortColors(nums: number[]): void {
    // 颜色分类和一般的排序不太一样，只有三种数字
    // 所以只需要把0放到左边，2放到右边即可
    const n = nums.length
    // 如果只用一个指针，则需要两趟遍历，一次把0放到头部，一次把1放到中间
    // 第一次遍历，处理0
    let p = 0
    for(let i = 0; i < n; i++){
        if(nums[i] === 0){
            let tmp = nums[p]
            nums[p] = nums[i]
            nums[i] = tmp 
            p++
        }
    }
    // 第二次遍历，处理1
    for(let i = p; i < n; i++){
        if(nums[i] === 1){
            let tmp = nums[p]
            nums[p] = nums[i]
            nums[i] = tmp 
            p++
        }
    }
};

解法二：双指针

/**
 Do not return anything, modify nums in-place instead.
 */
function sortColors(nums: number[]): void {
    // 颜色分类和一般的排序不太一样，只有三种数字
    // 所以只需要把0放到左边，2放到右边即可
    const n = nums.length
    // 双指针法只需要一次遍历
    let p0 = 0, p1 = 0 // p0负责交换0，p1负责交换1
    for(let i = 0; i < n; i++){
        if(nums[i] === 1){ // 如果碰到1就直接交换
            [nums[i], nums[p1]] = [nums[p1], nums[i]]
            p1++
        }else if(nums[i] === 0){
            [nums[i], nums[p0]] = [nums[p0], nums[i]]
            if(p0 < p1){ // 这种情况下会把1换走，所以要把1换回给p1
                [nums[i], nums[p1]] = [nums[p1], nums[i]]
            }
            p0++
            p1++
        }
    }
};