Sort Colors

75. 颜色分类

分析

经典的荷兰国旗问题，通过双指针和单次遍历的方式完成排序

将数组分为三个区域：

左区域（存放红色 0 的区域）
右区域（存放蓝色 2 的区域）
中间区域（存放白色 1 的区域）

使用三个指针：
- i: 指向左区域的边界
- j: 当前正在遍历的元素位置
- k: 指向右区域的边界
初始化 i = 0、j = 0、k = n-1
遍历数组，判断 \text{nums}[j] ：
- 如果是 1（白色），直接跳过，j++
- 如果是 0（红色），将 nums[j] 和 nums[i] 交换，i++, j++
- 如果是 2（蓝色），将 nums}[j] 和 nums}[k] 交换，k–- （注意：此时 j 不前进，继续检查新的 nums[j]
遍历结束后，数组即为排序后的结果

时间复杂度

整个数组只遍历了一次，时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

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


class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int i = 0, j = 0, k = nums.size() - 1; // 初始化指针
        while (j <= k) // 遍历直到中间指针超过右边界
        {
            if (nums[j] == 1) // 当前是白色，跳过
                ++j;
            else if (nums[j] == 0) // 当前是红色，交换到左区域
            {
                std::swap(nums[i], nums[j]);
                ++i, ++j;
            }
            else // 当前是蓝色，交换到右区域
            {
                std::swap(nums[j], nums[k]);
                --k;
            }
        }
    }
};