【力扣hot100题】（097）颜色分类
https://i-blog.csdnimg.cn/direct/d1fe1c840ba64a849033a7d5802dcb03.png第一眼感觉有点像确定不同元素个数的排序，但是要保证时间复杂度不超过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==0) count0++;
else if(nums==1) count1++;
else count2++;
}
for(int i=0;i<nums.size();i++){
if(count0-->0) nums=0;
else if(count1-->0) nums=1;
else nums=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==0){
swap(nums,nums);
ptr++;
}
}
ptr=nums.size()-1;
for(int i=nums.size()-1;i>=0;i--){
if(nums==2){
swap(nums,nums);
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==0){
swap(nums,nums);
ptr0++;
}
else if(nums==2){
swap(nums,nums);
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==0){
swap(nums,nums);
if(ptr0<ptr1) swap(nums,nums);
ptr0++;
ptr1++;
}
else if(nums==1){
swap(nums,nums);
ptr1++;
}
}
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]