LeetCode 75. 颜色分类

Categories:

Tags:

题目描述
思路分析
1. 解法一：三指针（荷兰国旗问题，推荐）
相似题目

题目描述

✅ 75. 颜色分类

思路分析

解法一：三指针（荷兰国旗问题，推荐）

核心思路：

经典的 Dijkstra 荷兰国旗算法，将数组原地划分为 [0区][1区][2区] 三段，一次遍历完成排序。

维护三个指针：low 指向下一个 0 应填入的位置，high 指向下一个 2 应填入的位置，mid 为当前扫描指针。

三个区间的不变量：[0, low) 全为 0，[low, mid) 全为 1，(high, n-1] 全为 2。

当 nums[mid] == 0：与 low 处元素交换，low++，mid++（low 处换来的必是 1，可安全前进）。

当 nums[mid] == 2：与 high 处元素交换，high--，mid 不动（high 处换来的值未知，需重新检查）。

当 nums[mid] == 1：已在正确区域，mid++。

循环条件为 mid <= high，一旦 mid > high 说明未知区域已处理完毕。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，只遍历一次数组

空间复杂度：O(1)，仅使用常数个指针变量，原地修改

class Solution {
    public void sortColors(int[] nums) {
        // low: 下一个 0 应放的位置，high: 下一个 2 应放的位置，mid: 当前扫描位置
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                // 将 0 交换到左侧 [0, low) 区域，low 和 mid 同步前进
                swap(nums, mid, low);
                low++;
                mid++;
            } else if (nums[mid] == 2) {
                // 将 2 交换到右侧 (high, n-1] 区域
                // mid 不前进，需重新检查当前位置的值
                swap(nums, mid, high);
                high--;
            } else {
                // nums[mid] == 1，已在正确区域，直接前进
                mid++;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

func sortColors(nums []int) {
    // low: 下一个 0 应放的位置，high: 下一个 2 应放的位置，mid: 当前扫描位置
    low, mid, high := 0, 0, len(nums)-1
    for mid <= high {
        if nums[mid] == 0 {
            // 将 0 交换到左侧区域，low 和 mid 同步前进
            nums[mid], nums[low] = nums[low], nums[mid]
            low++
            mid++
        } else if nums[mid] == 2 {
            // 将 2 交换到右侧区域，mid 不前进，需重新检查当前位置
            nums[mid], nums[high] = nums[high], nums[mid]
            high--
        } else {
            // nums[mid] == 1，已在正确区域，直接前进
            mid++
        }
    }
}

相似题目

题目	难度	考察点
283. 移动零	简单	双指针、原地移动
27. 移除元素	简单	双指针、原地删除
26. 删除有序数组中的重复项	简单	双指针
215. 数组中的第K个最大元素	中等	快速选择、三路划分
324. 摆动排序 II	中等	排序、三路划分
148. 排序链表	中等	链表、归并排序
905. 按奇偶排序数组	简单	双指针、分区

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/76545281