力扣精选算法100道——颜色分类(双指针和三指针俩种方法解决此题）

目录

🚩了解题意

🚩算法分析

第一种方法：双指针

🚩代码实现一

第二种方法：三指针

🚩代码实现二

---

🚩了解题意

本题将整数0，1，2代表红白篮，nums中的整数并不是按照红白蓝的顺序排列，我们要做的就是让nums中的整数按红白蓝排列，比如样例中的nums={2，0，2，1，1，0}最终按照红0白1篮2的顺序排列，最终的结果是{0，0，1，1，2，2}。

就是将0红排列在一起，1白排列在一起，2蓝排列在一起。

---

🚩算法分析

第一种方法：双指针

利用i进行遍历数组，ptr来进行划分范围，最终得到的结果是

[0,ptr-1] 红色

[ptr,size-1] 白色和蓝色

如果nums[i]==0的时候我们就将nums[i]的值和nums[ptr]的值交换，然后ptr++

i遍历完之后，我们看到所有的0都再最左边，再进行一次遍历，但是这时候的i是从ptr开始的

因为上面nums[i]和nums[ptr]交换位置之后，ptr++，所以ptr再下标2的位置。i从下标2开始进行。

如果遇到nums[i]==1的时候，我们就将nums[i]和nums[ptr]交换位置，ptr++。

---

🚩代码实现一

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

---

第二种方法：三指针

利用i来遍历数组，left作为左指针，right作为右指针

如果nums[i]==0,先让left++，然后与nums[i]和nums[left]交换位置，然后i++。

如果nums[i]==2,先让--right，然后与nums[i]和nums[right]交换位置。

注意：这里的i并不往后走，因为i是待扫描的区域，就是Num[i]是未知的数字，我们要继续判断nums[i]是等于多少，再进行一次判断。

此时继续判断nums[i]等于多少，此时的nums[i]==2，那么让right先--，然后交换nums[i]和nums[right]的值。

如果我们不知道nums[i]的值，我们就不能让i++.

如果nums[i]==1,我们直接就让i++

最终的循环判断条件就是 i<right即可，i与right相遇就结束循环。

---

🚩代码实现二

class Solution {
public:void sortColors(vector<int>& nums) {int left=-1,right=nums.size();int n=nums.size();int i=0;while(i<right){if(nums[i]==0)swap(nums[++left],nums[i++]);else if(nums[i]==1)i++;else swap(nums[--right],nums[i]);//此时的i不能++，因为i对应的值是未扫描的部分}}
};

---

关关难过。