（LeetCode C++）颜色分类

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

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

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

示例 1：

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

示例 2：

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

提示：

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

Method：

使用两个指针，分别指向红白交界和蓝白交界，然后依次遍历给定数组，将对应的数字交换即可。

Code：

class Solution{
public:
    // 颜色分类
    void sortColors(vector &nums){
        // 记录给定数组的长度
        int n=nums.size();

        // 如果数组的长度为1
        // 此时直接返回
        if(n<=1){
            return;
        }

        // 左边指针
        // 记录红白交界
        int left=0;
        // 右边指针
        // 记录白蓝交界
        int right=n-1;

        // 当前的位置索引
        int index=0;

        // 如果当前的位置小于右指针
        // 进行遍历
        while(index<=right){
            // 当前遍历值为0
            if(nums[index]==0){
                // 将当前值交换到左边界
                swap(nums[index],nums[left]);
                // 左边界向右移动一位
                left++;
            }
            // 当前遍历值为2
            else if(nums[index]==2){
                // 将当前值交换到右边界
                swap(nums[index],nums[right]);
                // 右边界向左移动一位
                right--;
                // 此时未确定交换到index的数的大小
                // 因此不可以遍历下一个
                continue;
            }
            // index向右移动一位
            // 遍历下一个值
            index++;
        }
    }

};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-colors