蓝桥杯---颜色分类（leetcode第75题）题解

1.问题重述

颜色分类，实际上就是赋予了三种颜色不同的数值，0,1,2分别代表的就是一个类型的颜色，我们题目说的是对于颜色进行分类，实际上就是对于0,1,2进行分类，我们把很多数字（其中这个里面包含了0,1,2）混合起来，然后需要按照规则对于这个里面的数据进行分类展示，返回分类之后的结果数组；

因为这个给的示例很容易理解，所以我就直接放在这个第一个话题下面了，下面我们就直接分析这个题目的思路：其实这个实例就是0放到最左边，1放到这串数据的中间，而这个2放到我们的最右边；

2.思路分析

我们通过i,left,right把这个数组分成了几个部分，每一个部分代表着不同的含义，例如这个i就是进行遍历我们这个数据的；

0全部放置到left左侧的区域；

2全部放置到right右边的区域；

left和i之间放置的就是1这个元素；

i和right之间的就是还没有进行分类的元素；

上面的这个就是我们进行分类的思路，如下图所示：

因为我们的i是负责扫描的，因此这个i可能会扫描到不同的数值，分别是0,1,2，对于不同的数值，我们需要采取不同的解决方案；

如果扫描到0，这个时候需要把它放到我们的left左边，因此这个时候让i指向的元素和left+1下标的元素进行交换，这个时候把0换到我们的left的左边的区域，然而这个i需要右移一下（因为从left+1交换过来的元素是1，我们的i扫描的时候应该是没有分类的元素，因此这个需要i++）

我们可以验证一下，即使这个i就是left+1下标，这个时候的交换就是我们的i自己和自己的交换，上面的这个思路依然是符合题目要求的；

如果扫描大1，这个时候就正合我意，因为我们上面已经说了，这个left和i之间的就是我们的1，因此这个时候i++移动一下继续扫描就可以了；

如果扫描到2，这个时候需要放到right的右边位置,也就是i和right-1下标进行交换，这个时候i交换过来的是right-1位置的元素，这个元素是没有分类的，因此这个不能像第一类里面的那个样子i再移动了，这个情况下我们的i原地不动，因为这个i指向的就是没有分类的元素；

3.代码分析

其实上面的这个思路复杂，可能需要我们进行讨论的这个情况比较多，但是这个代码真的很简单；

首先，我们需要定义一个swap函数，其实就是我们最开始学习C语言的时候，通过一个中间变量temp进行两个数据的交换；

接下来代码里面的if else就是根据这个i指向的不同的元素进行交换和移动就可以了，和上面的思路就是一样的；

其实我觉得通过这个题目我们可以反思一下：

其实这个题目的代码无非就是if else else，然后最上面就是我们学习C语言的时候就非常熟悉的两个数据交换的代码，就是这么简单的元素的拼合，就是这个算法题目的答案，是不是觉得也挺不可思议的，对于像我这样的小白而言，我觉得很震惊，这个里面的代码的逻辑并不是很复杂，但是这个从题目—》实现的过程的这个思路，实现，才是我们真正缺少的，应该反复实践的；