今天面试就先到这里吧，回去等通知吧！

通知：吴师兄学算法训练营第十期开启报名，预计 12 月 20 开营，解锁 400 题。

一、题目描述

给定一个包含红色、白色和蓝色、共 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

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

二、题目解析

这道题目有很多种解法。

但千万别做个“大聪明”，使用 sort 排序函数：

Arrays.sort(nums);

一行代码也通过了，但面试结果就是：今天面试就先到这里吧，回去等通知吧！

(图片来源于 LeetCode 75 号问题题解评论区）

因为题目有几个限制：

• 1、原地操作
• 2、不能使用代码库中的排序函数
• 3、常数级别的空间复杂度
• 4、扫描一遍

使用上面的 sort 函数就是和面试官较劲了。。。

这道题目是非常经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出，掌握这道题目对于后续学习快速排序、三指针等知识点非常有帮助。

直接来说解法。

设置 3 个索引，left 指向数组的开始位置，right 指向数组的结束位置，index 指向数组的开始位置。

我们让 index 从头开始向后移动，在移动的过程中，它指向的元素会出现三种情况：

• 如果 index位置上的元素值为 0，则说明是红色，要放在最前面去，此时最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换，交换完毕之后，说明 0 已经在它应该在的位置，即在整个数组的左区域，所以 left 可以向后移动，index 也向后移动

• 如果若 index 位置上的元素值为 1，则说明是白色，就应该放在中间，不用管它，继续移动 index

• 如果 index 位置上的元素值为 2，则说明是蓝色，要放在最后面，此时最后面的那个元素被 right 指着，所以让 index 指向的元素和 right 指向位置上的元素进行交换，交换完毕之后，说明 2 已经在它改在的位置，即在整个数组的右区域，right 向前移动，但由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种，到了 index 后，还需要继续观察一轮，所以 index 先不移动

三、参考代码

// LeetCode 100 题精讲：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
// 作者：程序员吴师兄
// 颜色分类（LeetCode 75）：https://leetcode.cn/problems/sort-colors/
class Solution {
    public void sortColors(int[] nums) {
        
        // left  指向数组的开始的位置，它指向的位置左侧都是 0
        int left = 0;

        // right  指向数组的结束的位置，它指向的位置右侧都是 2
        int right = nums.length - 1;

        // index 指向数组的开始位置
        int index = 0;

        // index 向后移动，当它越过 right 时跳出循环，不需要再判断了
        // 因为此时说明 index 右侧的都已经是 2
        while(index <= right){

            // 获取当前的元素值
            int cur = nums[index];
            
            // 如果 index 位置上的元素值为 0
            if(cur == 0){
              // 说明是红色，要放在最前面去
              // 最前面的那个元素被 left 指着，所以让 index 指向的元素和 left 指向位置上的元素进行交换
              swap(nums,left,index);

              // index 可以向后移动
              index++;
              // left 可以向后移动，它的左侧区域都是 0
              left++;

              // 如果 index 位置上的元素值为 1
            }else if(cur == 1){
                // 说明是白色，就应该放在中间，不用管它，继续移动 index
                index++;

                // 如果 index 位置上的元素值为 2
            }else if(cur == 2){

                // 说明是蓝色，要放在最后面
                // 所以让 index 指向的元素和 right 指向位置上的元素进行交换
                swap(nums,index,right);

                // 由于原先 right 指向的元素可能为 0、1、2 这三种的任何一种
                // 交换到了 index 后，还需要继续观察一轮，所以 index 先不移动
                right--;
            }
        }

    }

    // 通过中间变量，交换两个元素的值
    // nums[i] 的值变为了 nums[j] 的值 
    // nums[j] 的值变为了 nums[i] 的值 
    private void swap(int[] nums, int i ,int j){
        // 使用临时变量 temp，保存 nums[i] 的值
        int temp = nums[i];
        
        // nums[i] 的值修改为 nums[j] 的值
        nums[i] = nums[j];

        // nums[i] 的值修改为 temp 的值
        nums[j] = temp;
    }
}

提交通过。