(128)75. 颜色分类(leetcode)

题目链接： https://leetcode-cn.com/problems/sort-colors/ 难度：中等 75. 颜色分类 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶： 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？

最简单直接的方法 循环两次就可以了 其它的方法没想到 设置一个标志位（下标）第一次循环将所有的0移动到最前面 第二次将所有的1移动到前方

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

emmm，，， 就是这么简单 进阶的话 只使用一次循环 也不能说没想到方法 想是想到了但是错了 看了题解之后才明白是什么情况 将所有的0移动到前面 将所有的2移动到后面 设置两个指针 分别指向0和2的结束位置的下一个 （p0从0开始 p2从n-1开始） 我也是这么想的 结果。。。 在nums[ i ]==2的时候有一个问题，p2所指的位置的数字可能2 （所以这里要写一个循。。。。） 有点gou。

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

还有一个类似的方法 基本是一样的 设置p0，p1的位置 也有一个需要注意的地方 nums[i]==0 可能会将1交换出去 并且这里要将p0和p1同时加一

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