75. 颜色分类（荷兰旗问题）

题目

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

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

注意: 不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。你能想出一个仅使用常数空间的一趟扫描算法吗？

思路

这题实际上是荷兰旗问题，先介绍下荷兰旗问题：

荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示：

假设这样的条纹有多条，且各种颜色的数量不一，并且随机组成了一个新的图形，新的图形可能如下图所示，但是绝非只有这一种情况：

需求是：把这些条纹按照颜色排好，红色的在上半部分，白色的在中间部分，蓝色的在下半部分，我们把这类问题称作荷兰国旗问题。

题目要求一次遍历就可实现排序，那么就要求边遍历变排序，我们可以这样想，依次遍历每个元素：

nums[index] == 0 时，将 0 放在数组前面；nums[index] == 1 时，我们不错任何处理；nums[index] == 2 时，将 2 放在数组后面；

我们定义三个指针 idx1, idx2, index 来实现这个过程，index 表示遍历数组用到的下标值，idx1 表示 0~idx1 存放 0，每次的 0 添加到末尾，即 idx1++，idx2 表示 idx2~n-1 存放 2，每次的 2 添加到开头，即 idx2--；

具体代码如下：

代码

class Solution { public void swap(int[] nums, int x1, int x2){ // swap函数 int t = nums[x2]; nums[x2] = nums[x1]; nums[x1] = t; } public void sortColors(int[] nums) { int idx1 = 0, idx2 = nums.length-1, index = 0; while (index <= idx2) { if (nums[index] == 0){ swap(nums, idx1, index); idx1++; index++; // 这个步骤交换的必定是1和0，交换后的1我们不做处理，所以直接index++ } else if (nums[index] == 2){ swap(nums, idx2, index); idx2--; // 这里index一定不能+1，因为我们交换的可能是2和0，交换后，对于0还需要继续处理 } else index++; // 对于1，不做任何处理 } } }