/*
 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 
 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 
 注意:
 不能使用代码库中的排序函数来解决这道题。
 
 示例:
 
 输入: [2,0,2,1,1,0]
 输出: [0,0,1,1,2,2]
 */
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    void sortColors(vector<int>& nums) {
        //根据计数排序的思想，先遍历一遍数组，将==0和==1以及==2的数字个数统计出来，之后根据个数又赋值给数组相应的位置
        int count0=0;
        int count1=0;
        int count2=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==0)
                count0++;
            else if(nums[i]==1)
                count1++;
            else if(nums[i]==2)
                count2++;
        }
        int i=0;
        for(;i<count0;i++)
        {
            nums[i]=0;
        }
        for(;i<count0+count1;i++)
        {
            nums[i]=1;
        }
        for(;i<count0+count1+count2;i++)
        {
            nums[i]=2;
        }
    }
    //基于三路快速排序的思想，将==0,==1,==2进行分段处理
    void sortColors2(vector<int>& nums)
    {
        int zero=-1;    //nums[0...zero]==0
        int two=nums.size();    //nums[two...n-1]==2
        for(int i=0;i<two;) //这块不能写i++，因为当nums[i]的值为2的时候，交换完了之后不能i++，还要接着判断换过来的数字是几
        {
            if(nums[i]==1)
            {
                i++;
            }
            else if(nums[i]==2)
            {
                two--;
                swap(nums[i],nums[two]);
            }
            else
            {
                zero++;
                swap(nums[zero],nums[i]);
                i++;
            }
        }
    }
};
int main()
{
    vector<int> vec {0,1,2,2,2,2,0,1,1,0,0,1,1};
    Solution().sortColors2(vec);
    for(auto i: vec)
    {
        cout<<i<<" ";
    }
}