刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/sort-colors/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

思路

经典荷兰国旗问题。进阶要求只用一趟，那么就顺着这个要求来

首先思路其实很朴素：

把0放前面，把2放后面，中间剩下1

思路拆解

• 既然要把0放前面、2放后面，那就需要两个指针，分别指向放0、放2的位置
• 起一层循环遍历元素
• 对于2的处理，就是放到2的指针位置，并往前移动指针
• 对于0的处理，就是放到0的指针位置，并往后移动指针
• 对于1的处理，因为1其实本来就是在0、2两个指针中间的位置，无需处理

总体思路就是这个，但是确实有些细节需要注意，干说太抽象，请移步代码注释

有意思的其他思路分享

• 桶排序思路
  直接统计三个元素的数量，然后前x个是0，直接赋值0，后面y个是1，直接赋值1，最后剩下的全赋值2

• 桶排序思路变种
  统计三个元素数量后，每个数字的位置都有了自己的起始点，那么在遍历到元素时其实就确切的知道了应该放到什么位置了，也会很简单，并且代码也很清晰简明

且，时间复杂度会非常高，比一趟排序的方法快多了，哈哈哈

• 两趟交换
  第一趟只处理0，把0放前面，不区分1和2
  第二趟从上次结束位置开始，只处理1，把2放前面

至此

代码

func sortColors(nums []int) {
	// sp0 指向下一个放置 0 的位置，从前往后走
	// sp2 指向下一个放置 2 的位置，从后往前走
	sp0, sp2 := 0, len(nums)-1
	// 在上面两个参数的前提下，最终处理完时
	// [0, sp0-1] 是0的区间
	// [sp0, sp2] 是1的区间
	// [sp2+1, len(nums)-1] 是2的区间

	// <= sp2 防止越界
	for i := 0; i <= sp2; {
		// 2 需要往 sp2 位置去放，因为交换过来可能是0，可能是1
		// 而0需要去往sp0放，并使得sp0++，所以暂时先不移动i，再次判断
		if nums[i] == 2 {
			nums[i], nums[sp2] = nums[sp2], nums[i]
			sp2--
		} else if nums[i] == 0 {
			// 这里最难理解的就是为什么这时需要i++
			// 因为0需要交换到sp0的位置，sp0++
			// 如果 sp0 自加之前，i == sp0，
			//   自然是需要往后处理，当前值不需要再处理了，需要执行 i++
			// 如果 sp0 自加之前，i > sp0，那请思考，sp0位置会是2么？
			//   肯定不会，因为之前的位置都被 nums[i] == 2 的分支处理过了
			//   所以肯定是1，那1需要处理吗？并不需要，因为[sp0, sp2]本来就是1的区间
			//   就算是之后发现了0，移动了sp0，也是将原本 sp0 位置的 1 移动到了后边
			//   同样的，此时 sp0 和 i 之间不会存在非1，因为都已经被处理过了
			nums[i], nums[sp0] = nums[sp0], nums[i]
			sp0++
			i++
		} else {
			// 1 无需处理，详细解释见 nums[i] == 0 的分支注释
			i++
		}
	}

	// fmt.Printf("res: %v\n", nums)
}