LeetCode Hot 100 | 98. 颜色分类

LeetCode 75. 颜色分类 (Sort Colors)

1. 核心思路：两次扫描 + 双指针

本题要求对包含 0、1、2 的数组进行原地排序，等价于 荷兰国旗问题 的简化版本。

核心思想： 使用一个指针 current_index 维护「已排序部分的末尾位置」。

算法流程（两次扫描）：

第一轮扫描 —— 把 0 放到前面：

• 遍历数组，遇到值为 0 的元素，将其与 current_index 位置交换
• current_index++，指向下一个 0 应该存放的位置
• 结束后，所有 0 都在数组前部，current_index 指向第一个 1 应该放的位置

第二轮扫描 —— 把 1 放到 0 后面：

• 从数组开头重新遍历，遇到值为 1 的元素，将其与 current_index 位置交换
• current_index++，继续向后扩展已排序区域
• 剩余的元素自然就是 2，无需处理

2. 代码实现

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int current_index = 0;
        
        // 第一遍扫描：把所有 0 放到数组前面
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                swap(nums[i], nums[current_index]);
                current_index++;
            }
        }
        
        // 第二遍扫描：从 current_index 开始，把所有 1 放到 0 后面
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                swap(nums[i], nums[current_index]);
                current_index++;
            }
        }
        
        // 此时，2 已经自动排在最后，无需额外处理
    }
};

3. 关键细节备忘 (Key Takeaways)

1. current_index 的作用：

   • 第一轮结束后，[0, current_index-1] 区域全是 0
   • 第二轮结束后，[0, current_index-1] 区域包含所有的 0 和 1，且有序
   • 剩余的 [current_index, end] 自然全是 2

2. 最优解 —— 三指针一次扫描（荷兰国旗算法）：

   • 使用三个指针：left（0的右边界）、right（2的左边界）、i（当前扫描位置）
   • 一次遍历完成分类，遇到 0 放左边，遇到 2 放右边，遇到 1 跳过
   • 时间复杂度：$O(N)$ — 只需遍历一次
   • 空间复杂度：$O(1)$ — 原地排序

3. 两次扫描 vs 一次扫描：

   • 两次扫描代码更易理解，但常数较大（遍历两次）
   • 荷兰国旗算法更高效，但指针逻辑稍复杂

4. 复杂度分析（当前解法）：

   • 时间复杂度：$O(N)$ — 虽然遍历两次，但仍是线性时间
   • 空间复杂度：$O(1)$ — 原地排序，只使用常数额外空间