75. 颜色分类

mid

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

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

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

示例 1：

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]

单指针

可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 单指针
func sortColors(nums []int) {
	k := 0
	// 把所有0放到开头
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			nums[i], nums[k] = nums[k], nums[i]
			k++
		}
	}
	// 把所有1放到0后
	for i := k; i < len(nums); i++ {
		if nums[i] == 1 {
			nums[i], nums[k] = nums[k], nums[i]
			k++
		}
	}
}

双指针

使用两个指针分别用来交换 0 和 1，只要遍历一次就好啦

注意 p0 < p1 的情况，会把 1 换走，这时候要把这个 1 换到 p1 上

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 双指针
func sortColors(nums []int) {
	p0, p1 := 0, 0
	for i, num := range nums {
		if num == 0 {
			nums[i], nums[p0] = nums[p0], nums[i]
			if p0 < p1 {
				nums[i], nums[p1] = nums[p1], nums[i]
			}
			p0++
			p1++
		} else if num == 1 {
			nums[i], nums[p1] = nums[p1], nums[i]
			p1++
		}
	}
}