LeetCode#75

LeetCode#75颜色分类

题目链接
刚看题的时候还以为是个简单的双层暴力循环（比如冒泡或者选择排序），但是题目要求说不能有额外的空间复杂度且只能遍历一次emmmmmmm，后来想到了双指针的写法，一个代表0，一个代表1，只要把0和1都挪到最前面，那剩下的自然就是2了。
具体做法是，一个指针指向应该放0的位置，一个指针指向应该放1的位置，如果在遍历过程中找到了0或者1，则和相应的指针进行交换，同时这个指针向前移动。思路很简单，但是中间有一些细节需要处理：如果在找到一个0的时候，这个位置上已经是确定的1的位置（即1的指针已经遍历过了），那么直接进行交换就会让当前这个已经确定位置的1产生错误。如果当前p0指针位置是1，我们可以先把需要交换的0交换到p0，再把这个1交换到p1。至于如何判断是否发生了这种情况，我们可以判断p1是否大于p0，如果大于则一定发生（不明白在纸上划拉两下就懂了）
附代码：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int length = nums.size();
        int p0 = 0,p1 = 0;
        for(int i = 0 ; i < length ; i ++)
        {
            if(nums[i] == 0)
            {
                if(p1 > p0)
                {
                    swap(nums[i],nums[p0]);
                    swap(nums[i],nums[p1]);
                    p0++;
                    p1++;
                }
                else
                {
                    swap(nums[i],nums[p0]);
                    p0++;
                    p1++;
                }
            }
            else if(nums[i] == 1)
            {
                swap(nums[i],nums[p1]);
                p1++;
            }
        }
    }
};