目录
一、题目描述
二、解题思路
1、什么是荷兰国旗问题？
2、如何解决荷兰国旗问题？
三、参考答案
一、题目描述
颜色分类
给定一个包含红色、白色和蓝色、共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
进阶：
你能想出一个仅使用常数空间的一趟扫描算法吗？
二、解题思路
本题是一个经典的荷兰国旗问题。
1、什么是荷兰国旗问题？
"荷兰国旗问题"是计算机科学领域中的一个经典问题，由著名计算机科学家Edsger Dijkstra首次提出。该问题模型源于荷兰国旗的三色排列：红色、白色和蓝色。具体描述如下：假设有一系列球，分别涂有红色、白色和蓝色，这些球随机分布在一条直线上。荷兰国旗问题的目标是通过一种有效的方法对这些球进行排序，使得所有红色球位于最左侧，白色球居中，而蓝色球则位于最右侧，从而模拟荷兰国旗的水平条纹排列。
2、如何解决荷兰国旗问题？
荷兰国旗问题总共就三个颜色，所以我们想要区分开来，最少需要两条分隔线。这样，我们就可以定义两个分割线left、right，分割线left、right均包含白色，不包含红蓝色。left左边的是红色，右边是白色，right的左侧为白色，右侧为红色。在定义一个cur指针用来遍历每个球，根据球的颜色来决定它的位置。为了方便大家理解，如下就是一个演示过程：
1）此时遍历的是红色，红色需要在left的左侧，所以需要移动分割线left,并且移动cur指针。
2）此时遍历的是蓝色，蓝色需要在right的右侧，所以需要把当前cur指向的元素和分割线right所在的元素就行交换，并将分割线right左移，注意此时的cur不能移动，因为交换过来的元素并不知道他是什么颜色，所以也需要判断它的颜色，然后进行对应的操作。
3）此时和步骤1）一样是红色，所以一样的处理方式。
4）此时遍历的是白色，是在left的左边的，所以不需要移动分割线，只需要移动当前指针到下一个位置即可。
5）此时遍历的是蓝色，所以和步骤2）一样的处理。
6）经过步骤5）后当前指向的元素虽然还是蓝色，但是右分割线的位置已经往左移动了。此时还是继续和步骤2）一样的处理。
7）当前遍历的元素是白色，所以直接不做任何处理，只移动cur指针到下一位。
8）当前遍历的元素是红色，是不是还是应该像步骤1）一样直接往右移动分割线left，再将cur移向下一个元素呢？显然是不行的，此时，我们需要将cur指向的元素和分割线left所在位置的元素进行交互，然后在分别向右移动分割线left和cur指针。所以，当我们遍历到白色的时候，也是和遍历到蓝色一样需要加一个交换操作的。不同的是蓝色不需要移动当前指针cur，而白色需要移动当前指针cur(白色需要移动当前指针是因为，在cur指针左侧的都是判断过的，不需要再判断了)。
9）当前指针cur和分割线right相遇，也就是预示着处理完成。这时候也可以看到，我们已经完成了红白蓝的排序。
三、参考答案
本题其实就是荷兰国旗问题，此题的0其实就是荷兰国旗问题中的红色，1就是白色，2就是蓝色。按照上述分析的过程，不难写出如下代码：
class Solution {public void sortColors(int[] nums) {// 经典的荷兰国旗问题int l = 0, cur = 0, r = nums.length - 1;while (cur <= r) {if (nums[cur] == 0)swap(nums, l++, cur++);else if (nums[cur] == 1)cur++;elseswap(nums, cur, r--);}}// 定义交换数组的方法private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}此时的时间复杂度就是O(n)，而空间复杂度便是达到了O(1)，也就是满足了题目中的进阶的要求。
