75. 颜色分类

题目链接

这就是「荷兰国旗」问题，把颜色分成左边红色、中间白色、右边蓝色的顺序，实现快排的一部分步骤。

解题思路

• 我们可以有一个left_border变量，表示[0, left_border]都是红色，同时，一个right_border变量，[right_border, n - 1]都是蓝色，那么[left_border + 1, right_border - 1]就是白色了。
• 初始的时候，left_border = -1，表示还没有红色的，right_border = n，表示没有蓝色的。
• 我们从左往右遍历
  • 如果i是白色，则啥也不干，i++
  • 如果是红色，我们要「发货」到红色区域，还记得红色区域的位置吗？[0, left_border]，现在红色区域要多一个数，我们放在哪？放在left_border+1的位置，同时left_border++，表示红色区域扩大了。那么原来left_border+1的值怎么办？放到i位置。放过来之后呢？这个数需要处理吗？不需要，因为在操作之前[0, left_border]是红色，[left_border + 1, i - 1]是白色，所以left_border + 1本来就是白色的。
    • 总结一遍，如果i是红色，则swap(i, left_border + 1)，交换位置，同时left_border++，同时i++
  • 如果是蓝色呢？我们要「发货」到蓝色区域[right_border, n - 1]， 发货到right_border - 1，同时right_border--表示蓝色区域扩大了。原来的right_border - 1的数，换到i位置，要处理吗？要处理！为什么？因为我们是从左往右遍历的，right_border - 1的数，我们都还没看过，不知道是什么情况。
    • 总结一遍，如果i是蓝色，则swap(i, right_border - 1)，同时right_border--。
• 那什么时候终止遍历？当i == right_border的时候终止，因为[right_border, n - 1]都是蓝色了
• 在脑子里想一下，左边红色，中间白色，右边蓝色，然后两条分界线分成三部分，就很好理解了。

代码

class Solution {
public:
    void swap(vector<int>& nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    void sortColors(vector<int>& nums) {
        int left_border = -1;
        int right_border = nums.size();
        int i = 0;
        while(i < right_border) {
            if (nums[i] == 1) {    // 白色
                ++i;
            } else if(nums[i] == 0) {   // 红色  发货到红色区域
                swap(nums, i, left_border + 1);
                left_border++;
                i++;
            } else {     // 蓝色  发货到蓝色区域
                swap(nums, i, right_border - 1);
                right_border--;
                // 注意这里i不能动
            }
        }
    }
    
};

补充，为什么说这是快排的一部分？

• 快排其实就是以某个数num划分，划分成左边小于num，右边大于num，中间等于num，然后中间的已经相等了，所以[0, left_border]继续快排(递归)，[right_border, n - 1]继续快排就行了。
• 这里的某个数要随机取，否则会因为数据情况(本来就是升序或者降序时)，退化成O(n^2)
• 快排