題目已經提示可以一遍掃描了但是我還是沒有想到，其實雙指針的想法我已經有了，但是一想到有問題就覺得無法實現。這也揭示了我思維上的問題：用一種方法解決問題遇到困難第一件事情不是想著如何攻克而是想著換一種方法。對自己的思維也不自信。

我自己簡單了寫了一個兩遍掃描的程序：

class Solution { public:vector<int> cnt;void sortColors(vector<int>& nums) {cnt.resize(3,0);int n = nums.size();for(int i=0;i<n;++i){++cnt[nums[i]];}int idx = 0;for(int i=0;i<3;++i){for(int j=0;j<cnt[i];++j){nums[idx++] = i;}}} };

仔細研究了一下題解，題解給出了三種方法。第一種方法使用單指針需要遍歷兩次并沒有什么借鑒意義。后面兩種使用雙指針的方法比較值得學習。

方法一

使用雙指針，$p_0$用來保存0和1的分界，$p_1$用來1和2的分界，剛開始的時候$p_0$和$p_1$都是0，然后對整個數組進行掃描：

• 如果是1，先將當前元素和$p_1$指向的元素調換，然后$++p_1$
• 如果是0，先將當前元素和$p_1$指向的元素調換，如果$p_1$在$p_0$的前面，則說明需要將$p_1$所指向0和$p_0$指向的1進行交換。
• 如果是2，則不用處理

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] == 1){swap(nums[p1++], nums[i]);} else if(nums[i] == 0){swap(nums[p1], nums[i]);if(p1 > p0){nums[p0] = 0;nums[p1] = 1;}++p1; ++p0;}}} };

這種寫法的核心在于讓$p_1$作為分界點，如果是1的話進行特殊處理

方法二

使用$p_0$保存0和1的分界點，使用$p_2$保存1和2的分界點，然后初始的時候讓$p_0$為0，$p_2$為n-1遍歷數組：

• 如果為0，則將當前遍歷元素和$p_0$所指向的元素進行交換，并$++p_0$
• 如果為2，則將當前遍歷元素和$p_2$所指向的元素進行交換，并$??p_2$。但是我們不能就這樣遍歷下一個元素，因為我們不能確定交換以后當前指向元素是1，所以我們要繼續對當前元素進行處理
• 如果為1，不進行處理
  當遍歷到$p_2$的時候停止遍歷

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

雖然這道題比較簡單，但是我覺得這道題的價值在于為快速排序的三路劃分提供了一個比較好的方法，對于快速排序的每一次劃分，我們可以把和樞紐相等的放在中間，然后再分別處理小于樞紐的和大于樞紐的，這樣效率比較高。

總結

以上是生活随笔為你收集整理的75 颜色分类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。