57.【中等】颜色分类
文章发布较早，内容可能过时，阅读注意甄别。
# 题目来源：
# 题目
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
1
2
2
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
1
2
2
示例 3：
输入：nums = [0]
输出：[0]
1
2
2
示例 4：
输入：nums = [1]
输出：[1]
1
2
2
# 分析
使用三路快速排序法能快速解决
，这个问题是非常典型的，可以使用三路快速排序的 partition 思想解决的问题。因为，整个数组中只有 0, 1, 2 三种元素。如果我们把 1 当做标定点的话，就自然而然的可以把元素 0 当做是小于标定点的部分，元素 2 当做是大于标定点的部分。
所以，大家可以看出来，只要我们使用 1 当做标定点，只需要运行一遍三路快速排序的 partition 过程，就能完成任务了：）
注意，在这个过程中，我们不需要随机去选择标定点了，我们已经通过对问题的分析，明确了标定点就是 1。同时，我们也不需要一定把一个 1 放在整个数组的最左边。既然我们明确了标定点是 1，在算法循环过程中，每个待处理的元素，直接和 1 进行比较就好了。
在下面的代码中，循环不变量的定义是：
nums[0...zero] == 0
nums[zero + 1, i - 1] == 1
nums[two, n - 1] == 2
1
2
3
2
3
其实，变量 zero 相当于我们在三路快速排序算法中的 lt； 变量 two 相当于我们在三路快速排序算法中的 gt。 有了这个定义，相信理解了快速排序算法的 partition 的逻辑，可以很容易地写出正确的代码。
# 代码
class Solution {
public void sortColors(int[] nums) {
int zero = -1, i = 0, two = nums.length;
while(i < two){
if(nums[i] == 0){
zero ++;
swap(nums, zero, i);
i ++;
} else if (nums[i] == 2){
two --;
swap(nums, i, two);
}else{
i ++;
}
}
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i]= nums[j];
nums[j] = t;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
执行用时：0 ms, 在所有 Java 提交中击败了100.00%
1
上次更新: 2024/03/07, 20:33:54