讨论/《数组类算法》 - 颜色分类/
《数组类算法》 - 颜色分类

思路:遇到0则和前面的0指针zeroPos所指向的位置交换,遇到2则和2指针twoPos所指向位置交换,如果发现交换到当前位置i的元素还是0或者2,那就让i回退一位,在下一轮循环中再重新从这个位置检查交换。

 void sortColors(vector<int>& nums) {
        if(nums.size()<=0)
            return;
        //都代表了当前需要插入的位置
        int zeroPos=0;
        int twoPos=nums.size()-1;
        for(int i = 0;i<=twoPos;i++){
          if (nums[i] == 0)
                swap(nums[zeroPos++], nums[i]);
          if (nums[i] == 2)
                swap(nums[twoPos--], nums[i]);
          if (nums[i] != 1)
                i = max(zeroPos, i) - 1;//用max是为了保证i总在0指针的后面
        }
    }
1
展开全部 29 讨论