【力扣hot100题】（097）颜色分类

第一眼感觉有点像确定不同元素个数的排序，但是要保证时间复杂度不超过o（n），即只扫描一遍。

没思路于是看评论区，看到一种很快速的做法，虽然面试不保证通过就是了……

class Solution {
public:void sortColors(vector<int>& nums) {int count0=0;int count1=0;int count2=0;for(int i=0;i<nums.size();i++){if(nums[i]==0) count0++;else if(nums[i]==1) count1++;else count2++;}for(int i=0;i<nums.size();i++){if(count0-->0) nums[i]=0;else if(count1-->0) nums[i]=1;else nums[i]=2;}}
};

但想法还是很有意思的，记录一下。

之后还是没思路，于是看了答案……

答案是使用指针法，设置指针指向前面0元素的末尾，遍历数组时发现有0元素就与指针交换，然后指针后移一位。

按同样方法使所有2排到最后去。

这样要遍历两边数组，但是很通俗易懂。

class Solution {
public:void sortColors(vector<int>& nums) {int ptr=0;for(int i=0;i<nums.size();i++){if(nums[i]==0){swap(nums[ptr],nums[i]);ptr++;}}ptr=nums.size()-1;for(int i=nums.size()-1;i>=0;i--){if(nums[i]==2){swap(nums[ptr],nums[i]);ptr--;}}}
};

于是答案又给出了双指针的进阶做法，只遍历一遍，然后每次查看是否为0和2，交换就行。

这里我遇到了一点困难，不知道为什么会出错，这是我一开始的错误解法：

class Solution {
public:void sortColors(vector<int>& nums) {int ptr0=0;int ptr2=nums.size()-1;for(int i=0;i<nums.size();i++){if(nums[i]==0){swap(nums[ptr0],nums[i]);ptr0++;}else if(nums[i]==2){swap(nums[ptr2],nums[i]);ptr2--;}if(ptr2==i) return ;}}
};

后来想想终于想到了为什么出错，因为单指针时0是从前往后遍历，2是从后往前遍历，这里改成双指针是都是从前往后遍历，会出现交换的两个元素都是2，交换完后直接跳过了这样的错误。

然后我决定用0和1做指针。

有点难些因为遇到0的时候也要附带交换1的指针，所以遇到0的时候交换后要把交换出去的1换回来（如果0指针在1的后面也就是有1元素）。

class Solution {
public:void sortColors(vector<int>& nums) {int ptr0=0;int ptr1=0;for(int i=0;i<nums.size();i++){if(nums[i]==0){swap(nums[ptr0],nums[i]);if(ptr0<ptr1) swap(nums[ptr1],nums[i]);ptr0++;ptr1++;}else if(nums[i]==1){swap(nums[ptr1],nums[i]);ptr1++;}}}
};