【分治】颜色分类

75. 颜色分类

75. 颜色分类

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

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

​ 必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路：分治

​ 所谓分治，无非就是 将一个大问题，切分为多个有共同特征的子问题分别去解决，最后子问题解决了，大问题就解决了！最常见的分治思想就是排序算法中的快速排序以及归并排序！

​ 而其中快速排序这个算法在力扣上有个算法题，使用常见的优化快排也是过不了的，所以我们学完分治之后就要看看如何更进一步去优化快排，相当于填了拿那道算法题的坑！

​ 而为了解决那道快排题，我们先来通过这道题学习一下常见的分治思路！这道题其实也借鉴了以前我们在写 283. 移动零 这道题的时候，使用的一个双指针的方法，只不过这道题需要使用三个指针来操作！

​ 首先这道题有一个特征，就是整个数组是可以分为三个部分的，分别是 0、1、2 三个连续数字的板块，所以我们可以想办法用指针来维护它们的边界，于是就想到可以在遍历的时候，将属于哪个板块的数字，就加到哪个板块中，最后遍历完之后就是一个分块的数组！

​ 我们先定义两个指针 left 和 right，分别指向数组的开头的结尾，然后使用 i 来遍历数组，假设数组长度为 n，则此时其实我们可以把数组分为四部分：

• [0, left]：全都是 0。
• [left + 1, i - 1]：全都是 1。
• [i, right - 1]：待扫描的区间。
• [right, n - 1]：全都是 2。

​ 根据上面的划分情况，一开始的状态是这样子的：

接着就是不断的移动指针 i，那么 i 遇到的无非就是三种情况：元素为 0、元素为 1、元素为 2。下面我们就来分析一下整个过程：

• 当nums[i] = 0时：
  • 因为 [0, left] 区间都是 0，那么 nums[i] = 0 的话，我们就要扩大 0 的区间，就要让 nums[left + 1] 也变成 0，left 才能往后移动，但是此时 nums[left + 1] 位置的元素有两种情况：
    1. 如果 nums[left + 1] = 1 的话，那么直接交换 nums[left + 1] 和 nums[i]，并且让 left++ 即可。
    2. 如果 nums[left + 1] = 0 的话，此时只有一种情况，那就是 i == left+1，因为 nums[left + 1] 是 0 的情况，i 肯定是先走过了，left 也一定走到了 i 之前覆盖的所有 0 的情况了，但是此时 nums[left + 1] 为 0，只能说明它就是一个待扫描的元素，也就是 i，此时我们交换 nums[left + 1] 和 nums[i]，其实就相当于 i 在自己交换自己，所以此时交换完之后不仅要让 left++，我们还要让 i++ 才行。
  • 综上所述，我们 要执行的操作就是 swap(nums[++left], nums[i++])，注意这里是先让 left 向后移动，然后交换完之后再让 i 向后移动！
• 当nums[i] = 1时：
  • 这种情况是最简单的，因为 [left, i - 1] 区间内都是 1，我们 只需要让 i++ 即可让当前的 1 落到新的 [left, i - 1] 区间内！
• 当nums[i] = 2时：
  • 因为 [right - 1, n - 1] 区间都是 2，所以此时我们要让 2 的区间扩大的话，就是让 right 向左移动，那么同样也会遇到和 left 一样的两种情况，这里就不讨论了，直接给出结论：swap(nums[--right], nums[i])。
  • 要注意的是，上面唯一不同的就是 交换完之后 i 是不需要移动的，因为本身 nums[right - 1] 就是一个待扫描的元素，所以此时 i 拿到的就是一个待扫描的元素，所以不需要向后移动，这个要注意！

​ 还要注意的是，i 只需要遍历到 right 即可，而不是遍历到 n，因为如果遍历到 n 的话，就会走到全都为 2 的区间，此时就会和 nums[right - 1] 也就是 1 进行交换，顺序就颠倒了！

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = n, i = 0;
        while(i < right) // 注意这里是小于right，不然后面的2部分又会和1部分交换过来
        {
            if(nums[i] == 0)
                swap(nums[++left], nums[i++]);
            else if(nums[i] == 1)
                i++;
            else
                swap(nums[--right], nums[i]); // 注意i不需要移动
        }
    }
};