75. 颜色分类

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

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

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

 

示例 1：

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

思路

遍历数组，维护三个指针red、white和blue，分别指向红色、白色和蓝色区域的边界。初始时，red和white指向数组开头，blue指向数组尾部。

遍历过程中，如果遇到红色元素，将其与red指针指向的白色元素交换，并将red和white指针向后移动一位；如果遇到白色元素，将white指针向后移动一位；如果遇到蓝色元素，将其与blue指针指向的白色元素交换，并将blue指针向前移动一位。

遍历结束时，红色区域的元素都在数组的左侧，蓝色区域的元素都在数组的右侧，白色区域的元素都在中间，即完成了排序。

class Solution {
public:
    void sortColors(vector<int> &nums){
        const int numsSize = nums.size();

        int red = 0; // 红色区域边界
        int white = 0; // 白色区域边界
        int blue = numsSize - 1; // 蓝色区域边界
        
        while (white <= blue) {
            if (nums[white] == 0) {
                // 将红色元素与白色元素交换，并将红色区域边界和白色区域边界向后移动一位
                swap(nums[white], nums[red]);
                red++;
                white++;
            } else if (nums[white] == 2) {
                // 将蓝色元素与白色元素交换，并将蓝色区域边界向前移动一位
                swap(nums[white], nums[blue]);
                blue--;
            } else {
                // 遇到白色元素，将白色区域边界向后移动一位
                white++;
            }
        }
    }
};