📑 题目：75. 颜色分类

🚀 本题 LeetCode 传送门

题目大意

抽象题意其实就是排序。这题可以用快排一次通过。

解题思路

题目末尾的 Follow up 提出了一个更高的要求，能否用一次循环解决问题？这题由于数字只会出现 0，1，2 这三个数字，所以用游标移动来控制顺序也是可以的。具体做法：0 是排在最前面的，所以只要添加一个 0，就需要放置 1 和 2。1 排在 2 前面，所以添加 1 的时候也需要放置 2 。至于最后的 2，只用移动游标即可。

这道题可以用计数排序，适合待排序数字很少的题目。用一个 3 个容量的数组分别计数，记录 0，1，2 出现的个数。然后再根据个数排列 0，1，2 即可。时间复杂度 O(n)，空间复杂度 O(K)。这一题 K = 3。

这道题也可以用一次三路快排。数组分为 3 部分，第一个部分都是 0，中间部分都是 1，最后部分都是 2 。

代码

package leetcode
func sortColors(nums []int) {
 zero, one := 0, 0
 for i, n := range nums {
  nums[i] = 2
  if n <= 1 {
   nums[one] = 1
   one++
  }
  if n == 0 {
   nums[zero] = 0
   zero++
  }
 }
}