目錄

🚩了解題意

🚩算法分析

第一種方法：雙指針

🚩代碼實(shí)現(xiàn)一

第二種方法：三指針

🚩代碼實(shí)現(xiàn)二

---

🚩了解題意

本題將整數(shù)0，1，2代表紅白籃，nums中的整數(shù)并不是按照紅白藍(lán)的順序排列，我們要做的就是讓nums中的整數(shù)按紅白藍(lán)排列，比如樣例中的nums={2，0，2，1，1，0}最終按照紅0白1籃2的順序排列，最終的結(jié)果是{0，0，1，1，2，2}。

就是將0紅排列在一起，1白排列在一起，2藍(lán)排列在一起。

---

🚩算法分析

第一種方法：雙指針

利用i進(jìn)行遍歷數(shù)組，ptr來(lái)進(jìn)行劃分范圍，最終得到的結(jié)果是

[0,ptr-1] 紅色

[ptr,size-1] 白色和藍(lán)色

如果nums[i]==0的時(shí)候我們就將nums[i]的值和nums[ptr]的值交換，然后ptr++

i遍歷完之后，我們看到所有的0都再最左邊，再進(jìn)行一次遍歷，但是這時(shí)候的i是從ptr開(kāi)始的

因?yàn)樯厦鎛ums[i]和nums[ptr]交換位置之后，ptr++，所以ptr再下標(biāo)2的位置。i從下標(biāo)2開(kāi)始進(jìn)行。

如果遇到nums[i]==1的時(shí)候，我們就將nums[i]和nums[ptr]交換位置，ptr++。

---

🚩代碼實(shí)現(xiàn)一

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來(lái)遍歷數(shù)組，left作為左指針，right作為右指針

如果nums[i]==0,先讓left++，然后與nums[i]和nums[left]交換位置，然后i++。

如果nums[i]==2,先讓--right，然后與nums[i]和nums[right]交換位置。

注意：這里的i并不往后走，因?yàn)閕是待掃描的區(qū)域，就是Num[i]是未知的數(shù)字，我們要繼續(xù)判斷nums[i]是等于多少，再進(jìn)行一次判斷。

此時(shí)繼續(xù)判斷nums[i]等于多少，此時(shí)的nums[i]==2，那么讓right先--，然后交換nums[i]和nums[right]的值。

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

如果nums[i]==1,我們直接就讓i++

最終的循環(huán)判斷條件就是 i<right即可，i與right相遇就結(jié)束循環(huán)。

---

🚩代碼實(shí)現(xiàn)二

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]);//此時(shí)的i不能++，因?yàn)閕對(duì)應(yīng)的值是未掃描的部分}}
};

---

關(guān)關(guān)難過(guò)。