75 颜色分类

一、题目

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

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

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

二、题解

2.1 计数排序（两次遍历）

这道题说到底只有 0、1、2 三种数字。最直观的想法就是：先数一数这三种数字各有多少个，然后按顺序重新填入数组即可。

class Solution {
    public void sortColors(int[] nums) {
        // 1. 统计 0, 1, 2 的数量
        int count0 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }

        // 2. 根据数量，重新重写数组
        for (int i = 0; i < nums.length; i++) {
            if (i < count0) {
                nums[i] = 0; // 前 count0 个全填 0
            } else if (i < count0 + count1) {
                nums[i] = 1; // 接下来 count1 个全填 1
            } else {
                nums[i] = 2; // 剩下的全填 2
            }
        }
    }
}

时间复杂度：$O(n)$（两次遍历数组：一次计数、一次重写）

空间复杂度：$O(1)$（只用了三个计数变量）

2.2 三指针法（一次遍历）

“荷兰国旗”问题标准解法：维护左右两个边界，加上一个游标。

你可以想象 0 必须放在最左边，2 必须放在最右边，1 被夹在中间。

• left 指针：指向当前排好序的 0 的最右侧边界。
• right 指针：指向当前排好序的 2 的最左侧边界。
• i 游标：从左到右遍历数组。

class Solution {
    public void sortColors(int[] nums) {
        int left = 0;               // 0 的右边界
        int right = nums.length - 1;// 2 的左边界
        int i = 0;                  // 当前遍历的游标

        // 注意：这里是 i <= right，因为 right 右边全是处理好的 2，不需要再看了
        while (i <= right) {
            if (nums[i] == 0) {
                // 遇到 0，把它扔到左边的 left 位置，然后 left 和 i 都往后走
                swap(nums, left, i);
                left++;
                i++;
            } else if (nums[i] == 1) {
                // 遇到 1，它本来就该待在中间，不用管，游标继续往前走
                i++;
            } else if (nums[i] == 2) {
                // 遇到 2，把它扔到右边的 right 位置，right 往左缩
                // 【核心细节】：此时 i 不能加 1！
                // 因为从 right 换过来的那个新数字还没有被检查过，下一步还要继续判断它！
                swap(nums, right, i);
                right--;
            }
        }
    }

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

时间复杂度：$O(n)$（游标 i 与 right 相遇即结束，每个元素最多被处理一次）

空间复杂度：$O(1)$（原地交换，只用常数个指针变量）