持续创作，加速成长！这是我参与「掘金日新计划 · 6 月更文挑战」的第14天，点击查看活动详情
本次刷题日记的第 60 篇，力扣题为：75. 颜色分类，中等
一、题目描述：
颜色分类，红橙黄绿青蓝紫，咱们咋区分嘞
二、这道题考察了什么思想？你的思路是什么？
仔细看看这个题，我们如何去做颜色分类：
- 题目中给出了一个数组，数组中有多个元素，元素的值只有 3 个情况，0,1,2 ，分别代表着红色，白色，蓝色
- 题目要求我们按照红白蓝的顺序排序数组，且不能使用 golang 提供的 sort 库函数
分析
如何来看这个题目呢，看上去好像很简单的样子，但是为啥是中等题呢，肯定有一定的弯弯绕绕
其实咱们简单的使用是 sort 来排序，从小到大排序一波就搞定了，但是咱们现在不能用了，肯定有别的方式
这里我们知道颜色的种类一共就 3 种，那么我们是不是其实就是对这 3 种颜色排序就可以了，那么我们很容易想到将 0 对应的颜色丢到 左边， 2 对应的颜色丢到 右边，那么剩下的 1 对应的颜色就在中间了，就像这样：
我们知道需要将上面一排的数组，转换成下面一排的数组，但是要如何做的？
题目要求我们在原地进行转换，我们是不是就可以定一个指针，将 2 放到尾巴后面，定义一个指针将 0 放到前面，剩下的 1 就默认在中间的
那么思考一下，我们就可以使用双指针的方式
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
需要注意，遍历数组的时候，咱们定义双指针的时候，是头一个指针，尾巴一个指针，若是 0 就放到头指针上，并向后偏移一位，若是 2 则放到尾巴指针上，且尾巴指针向前移动一位
编码如下：
func sortColors(nums []int) { p0, p2 := 0, len(nums)-1 for i := 0; i <= p2; i++ { for ; i <= p2 && nums[i] == 2; p2-- { nums[i], nums[p2] = nums[p2], nums[i] } if nums[i] == 0 { nums[i], nums[p0] = nums[p0], nums[i] p0++ } } }
四、总结：
这种实现方式，时间复杂度是多少呢？
实际的循环是在最外层的大循环上面，因此时间复杂度是 O(n)
空间复杂度度是 O(1) ，因为我们没有引入新的空间消耗
原题地址：75. 颜色分类
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
