Sitch's Blog
0%

LeetCode-No-75

发表于 分类于 Valine：

颜色分类

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

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

示例:

输入:** [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void sortColors(vector<int& nums) 
    {
        int left=0;
        int right=nums.size()-1;
        int cur=0;
        while(cur<=right)
        {   
            if(nums[cur]==0)//这个数字是0，移动0区域内，
            {
                swap(nums[cur],nums[left]);
                //假如curleft，left交换过来的值肯定已经被处理过了，但是处理时产生交换，原left指向的，一定是不用处理的吗？
                //jeromememory：准确的说 cur 如果 与 p0 不是指向同一个索引，那 cur 指向的索引值如果发生交换，那交换过来的一定是 1（原因是只有当遍历过的节点有1，p0 和 cur 才不会同步），而 如果索引是 1 刚好也就不用有任何操作，所以可以直接++。
                //假如cur==left==0，没啥好说的，下一个
                //假如cur<left, 可能吗？cur++的机会 = left++的机会
                left++;
            }
            else if(nums[cur]==2)//这个数字是2，移到2区域内
            {
                swap(nums[cur],nums[right]);
                right--;
                //交换过来的值，是右边过来的，cur没处理过，因此还需要对这个位置处理，--抵消++，位置不变
                cur--;
            }
            cur++;
        }
    }
};