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

第一眼感觉有点像确定不同元素个数的排序，但是要保证时间复杂度不超过o（n），即只扫描一遍。
没思路于是看批评区，看到一种很快速的做法，虽然面试不保证通过就是了……

1. class Solution {
2. public:
3.     void sortColors(vector<int>& nums) {
4.         int count0=0;
5.         int count1=0;
6.         int count2=0;
7.         for(int i=0;i<nums.size();i++){
8.             if(nums[i]==0) count0++;
9.             else if(nums[i]==1) count1++;
10.             else count2++;
11.         }
12.         for(int i=0;i<nums.size();i++){
13.             if(count0-->0) nums[i]=0;
14.             else if(count1-->0) nums[i]=1;
15.             else nums[i]=2;
16.         }
17.     }
18. };

复制代码

但想法还是很有意思的，记录一下。
之后还是没思路，于是看了答案……
答案是使用指针法，设置指针指向前面0元素的末端，遍历数组时发现有0元素就与指针互换，然后指针后移一位。
按同样方法使所有2排到末了去。
如许要遍历两边数组，但是很通俗易懂。

1. class Solution {
2. public:
3.     void sortColors(vector<int>& nums) {
4.         int ptr=0;
5.         for(int i=0;i<nums.size();i++){
6.             if(nums[i]==0){
7.                 swap(nums[ptr],nums[i]);
8.                 ptr++;
9.             }
10.         }
11.         ptr=nums.size()-1;
12.         for(int i=nums.size()-1;i>=0;i--){
13.             if(nums[i]==2){
14.                 swap(nums[ptr],nums[i]);
15.                 ptr--;
16.             }
17.         }
18.     }
19. };

复制代码

于是答案又给出了双指针的进阶做法，只遍历一遍，然后每次查看是否为0和2，互换就行。
这里我遇到了一点困难，不知道为什么会出错，这是我一开始的错误解法：

1. class Solution {
2. public:
3.     void sortColors(vector<int>& nums) {
4.         int ptr0=0;
5.         int ptr2=nums.size()-1;
6.         for(int i=0;i<nums.size();i++){
7.             if(nums[i]==0){
8.                 swap(nums[ptr0],nums[i]);
9.                 ptr0++;
10.             }
11.             else if(nums[i]==2){
12.                 swap(nums[ptr2],nums[i]);
13.                 ptr2--;
14.             }
15.             if(ptr2==i) return ;
16.         }
17.     }
18. };

复制代码

后来想想终于想到了为什么出错，由于单指针时0是从前往后遍历，2是从后往前遍历，这里改成双指针是都是从前往后遍历，会出现互换的两个元素都是2，互换完后直接跳过了如许的错误。
然后我决定用0和1做指针。
有点难些由于遇到0的时候也要附带互换1的指针，以是遇到0的时候互换后要把互换出去的1换回来（如果0指针在1的后面也就是有1元素）。

1. class Solution {
2. public:
3.     void sortColors(vector<int>& nums) {
4.         int ptr0=0;
5.         int ptr1=0;
6.         for(int i=0;i<nums.size();i++){
7.             if(nums[i]==0){
8.                 swap(nums[ptr0],nums[i]);
9.                 if(ptr0<ptr1) swap(nums[ptr1],nums[i]);
10.                 ptr0++;
11.                 ptr1++;
12.             }
13.             else if(nums[i]==1){
14.                 swap(nums[ptr1],nums[i]);
15.                 ptr1++;
16.             }
17.         }
18.     }
19. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。