问题描述 链接到标题

75.颜色分类

解题思路 链接到标题

这里，我们需要三个指针l, r, idx, l用来存放0,r用来存放2，idx用来进行遍历数组。

要注意的是，在遍历数组时:

  • if nums[idx] == 0，需要交换nums[idx]和nums[l]的值，同时idx++; l++;
  • if nums[idx] == 1，idx++即可
  • if nums[idx] == 2，需要交换nums[idx]和nums[l]的值，但此时只是r--，不会idx++，这是因为新的交换后的nums[idx]的值可能是0、1、2中的任意一个，因此还需要重新判断nums[idx]
  • 如果idx == l，那么[0, idx]区间范围内的数都是0，如果idx != l，那么[0, l - 1]区间范围内都是0，[l, idx)区间范围内都是1，因此可以进行idx++;

代码 链接到标题 

class Solution {
  public:
    void sortColors(vector<int> &nums) {
        int tmp = 0, index = 0;
        int l = 0, r = nums.size() - 1;
        while (index <= r) {
            if (nums[index] == 0) {
                tmp = nums[l];
                nums[l++] = 0;
                nums[index++] = tmp;
            } else if (nums[index] == 2) {
                tmp = nums[r];
                nums[r--] = 2;
                nums[index] = tmp;
            } else
                index++;
        }
    }
};