[LeetCode][Golang]|[LeetCode][Golang] 75. 颜色分类
题目：
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
【[LeetCode][Golang]|[LeetCode][Golang] 75. 颜色分类】我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例：
输入： nums = [2,0,2,1,1,0]
输出： [0,0,1,1,2,2]n == nums.length1 <= n <= 300nums[i]为0、1或2
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
func sortColors(nums []int) {
left, i, right := 0, 0, len(nums)-1
// 不变量： left之前（不包含nums[left]）均为0，right之后（不包含nums[right]）均为2
// all in [0,left) == 0
// all in [left,i) == 1
// all in (right,len) == 2
for i <= right {
if nums[i] == 0 {
nums[left], nums[i] = nums[i], nums[left]
left++
i++
} else if nums[i] == 2 {
nums[right], nums[i] = nums[i], nums[right]
right--
} else {
i++
}
}
}我们可以借鉴快速排序的思想对问题进行分析。首先设置循环不变量如下：
[0,left) == 0，即left之前（不包括nums[left]）不包含元素0之外的元素。[left,i) == 1，即left和目前循环到的i之间不包含元素1之外的元素。(right,len) == 2，即right之后（不包括nums[right]）不包含元素2之外的元素。
- 初始
left设为0，i设为0，right设为len-1，则为0的区间是[0,0)，不包含元素。为1的区间是[0,0)，不包含元素。为2的区间是(len-1,len)，不包含元素。所以初始状态满足不变式要求。 - 接下来的循环中，根据
nums[i]的值进行维护不变式的操作。分为以下三种情况
- 当
nums[i]为0时，交换nums[i]和nums[left]，并使left和i后移，满足不变式。 - 当
nums[i]为1时，后移i，满足不变式。 - 当
nums[i]为2时，交换nums[i]和nums[right]，并使right前移，满足不变式。注意交换后是nums[right]的值接受了本次循环的值判断，而交换后的nums[i]的值并没有接受值判断，所以不执行i的后移操作，需要在下一次循环中根据其值处理。
- 当
- 由于后两个区间中
i和right均为开区间，若当i == right循环停止，则元素nums[i]也可以说是元素nums[right]没有经过分类处理，因此最终循环终止条件为i <= right，这样才能保证数组中的每个元素均被处理过，且最终三个区间均满足不变式，算法成立。
- 时间复杂度：
O(n)，其中n是数组nums的长度。 - 空间复杂度：
O(1)。我们只需要常数的空间存储若干变量。
推荐阅读
- [LeetCode][Golang] 80. 删除有序数组中的重复项 II
- LeetCode-179-最大数
- [LeetCode][Golang] 26. 删除有序数组中的重复项
- golang常用库包（Go依赖注入(DI)工具-wire使用）
- Golang中的嵌套结构代码示例解释
- golang-grpc
- Leetcode18四数之和(双指针法)
- 如何在Golang中修剪字符串（）
- C++实现LeetCode(80.有序数组中去除重复项之二)
- Facebook|Facebook 开源 Golang 实体框架 Ent 现已支持 TiDB