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

进阶：

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

本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。

分类交换，跳跃处理

步骤：

1. 定义两个指针 start 和 end，start 表示 0 数组的右边界+1，end 表示 2 数组的左边界-1。
2. 用指针 i 从左到右遍历
   • 遇到 2，就把它和 end 处的元素（可能是0、1、2）交换，然后 end--。i 右侧是未知，所以需要循环处理。
   • 遇到 0，就把它和 start 处的 1 交换，然后 start++。i 左侧是已知的，所以不需要循环处理。
   • [0, start-1] 全是 0，[start, i-1] 全是 1，[i, end] 有0、1、2，[end+1, n-1] 全是 2。

class Solution {
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void sortColors(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            // 从左到右，一定要先处理大的，再处理小的，因为我们遇到大数要把它放到末尾，遇到小数不用动。把大数换到末尾有可能换过来一个小数，即大数是自变量。
            // 为什么不是遇到小数把它放到末尾？因为题目要求按照红、白、蓝的顺序排列，这对应升序排列。
            while (i < end && nums[i] == 2) {
                swap(nums, end, i);
                end--;
            }
            // 因为是从左到右遍历，所以 i 左边的数一定是升序的，即 [0,start-1] 全是 0，[start,i-1] 全是 1。所以遇到 0 就把它和 start 处的 1 交换一次即可。
            // 无需循环交换。因为上面的 while 已经为这里开好路了，上面是探路，所以需要循环处理复杂情形。
            if (nums[i] == 0) {
                swap(nums, start, i);
                start++;
            }
        }
    }
}

这解法有两个重点：

1. i < end，即保证 end 位于 i 后面，为什么不用写 start < i？因为 i 每轮都会自增，但是 start 是有条件自增，所以 start 一定在 i 左边。
2. 用 while 而不是 if，不然 nums=[2,1,2] 会出错，即把第一个 2 和末尾值交换完就停止了，交换完还是 [2,1,2]，应该一直交换， 直到把一个不是 2 的数交换到第一个位置。

分类赋值，线性处理，磨光，懒汉

这道题的关键是我们不在乎顺序，只在乎数量。因此我们可以打乱原有顺序，通过移动指针来记录数量信息。例如遇到了1，则n1处变为1，然后n1右移。

步骤：

1. 初始化两个指针 n0 和 n1，n0 表示 0 数组的右边界+1，n1 表示 0、1 数组的右边界+1。
2. 遍历数组中的每个元素：
   • 先将当前元素设置为 2。懒汉模式
   • 如果当前元素小于 2，说明 0、1 数组壮大，就将 nums[n1] 设置为 1，然后 n1 右移。
   • 如果当前元素小于 1，说明实际壮大的是 0 数组，就将 nums[n0] 设置为 0，然后 n0 右移。

class Solution {
    public void sortColors(int[] nums) {
        // n0 表示下一个 0 应该放置的位置索引，它表示0数组的右边界+1
        // n1 表示下一个 1 应该放置的位置索引，它表示0、1数组的右边界+1
        int n0 = 0, n1 = 0;

        // 遍历数组中的每一个元素。每个指针只做两件事，赋值和前进，只不过对于0和1，这两个操作是有条件执行的，遇到2则是无条件执行。
        // 一次遍历同时操作三个指针
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];  // 取出当前遍历的元素

            // 先将当前位置设置为 2，因为在最坏情况下，
            // 当前元素 num 可能会被最终设置为 2
            nums[i] = 2;

            // 如果当前元素是 0 或 1
            if (num < 2) {
                // 如果 num 是 0 或 1，说明 num 应该出现在 n1 的位置。
                // 然后，n1 位置的元素后移（逐步将 1 移动到正确位置）。
                nums[n1++] = 1;
            }

            // 如果当前元素是 0
            if (num < 1) {
                // 如果 num 是 0，说明 0 应该出现在 n0 的位置。
                // 逐步将 0 移动到正确位置。
                nums[n0++] = 0;
            }
        }
    }
}