每日一題系列（day 12）
前言：
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
?? ????如果說代碼有靈魂，那么它的靈魂一定是????算法????，因此，想要寫出??優(yōu)美的程序??，核心算法是必不可少的，少年，你渴望力量嗎????，想掌握程序的靈魂嗎???那么就必須踏上這樣一條漫長的道路????，我們要做的，就是斬妖除魔????，打怪升級！????當(dāng)然切記不可??走火入魔??，每日打怪，拾取經(jīng)驗(yàn)，終能成圣????！開啟我們今天的斬妖之旅吧！????
題目：
??給定一個包含紅色、白色和藍(lán)色、共 n 個元素的數(shù)組 nums ，原地對它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。
我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。
必須在不使用庫內(nèi)置的 sort 函數(shù)的情況下解決這個問題。
示例：
提示：
- n == nums.length
- 1 <= n <= 300
- nums[i] 為 0、1 或 2
思路：
??這題要求我們將三種顏色排好序，其實(shí)也就是對0，1，2的劃分而已，如果你看了我前面寫的題目的話，有一題 移動0 與這題很類似，都是類似于快排操作的實(shí)現(xiàn)，只不過在這里多了一個區(qū)間而已。
??其實(shí)解決這題我們可以仿照解決移動0的問題，移動0使用雙指針解決，這題有三種數(shù)據(jù)類型，我們可以多加一個指針，三指針來解決。
??1、首先，我們可以將數(shù)據(jù)分為3個區(qū)間，左中右，左邊放0，中間放1，右邊放2，用指針left指向最后一個被遍歷到的0元素，指針right指向最后一個被遍歷到的2元素，指針i用來遍歷數(shù)組（左右區(qū)間劃分ok了，中間的1也就ok了）
??2、left最開始指向-1，當(dāng)i遍歷到的元素為0時，先++left，在交換他倆的元素，i再自增。right最開始指向最后一個元素的下一個位置，如果i遍歷到的值為2，則先–right再交換他倆元素，這里我們不能將i自增，因?yàn)檫@個時候不確定交換過后的元素是否為0，還需要再判斷。
??3、最后，當(dāng)i指針與right指針相遇了，right往后全是2元素，所以這個時候循環(huán)就結(jié)束了。
代碼實(shí)現(xiàn)：
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int left = -1, right = n, i = 0;
while(i < right)//不結(jié)束一直循環(huán)
{
if(nums[i] == 0) swap(nums[++left], nums[i++]);//由i值判斷當(dāng)前該如何處理，是用左指針還是右指針
else if(nums[i] == 1) ++i;
else swap(nums[--right], nums[i]);
}
}
};
文章來源：http://www.zghlxwxcb.cn/news/detail-755932.html
??這題被標(biāo)為了中等，還是有一定難度的，但是如果你很熟悉快排的過程那么這題對你來說就是小case了，因?yàn)檫@題其實(shí)就是以1為基準(zhǔn)值，0甩到左邊，2甩到右邊，很多東西都是融匯貫通的。文章來源地址http://www.zghlxwxcb.cn/news/detail-755932.html
到了這里，關(guān)于每日一題：LeetCode-75. 顏色分類的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
