題目描述
給定一個(gè)包含紅色宛琅、白色和藍(lán)色，一共 n 個(gè)元素的數(shù)組逗旁，原地對(duì)它們進(jìn)行排序嘿辟，使得相同顏色的元素相鄰，并按照紅色片效、白色红伦、藍(lán)色順序排列。
此題中淀衣，我們使用整數(shù) 0昙读、 1 和 2 分別表示紅色、白色和藍(lán)色膨桥。
注意:
不能使用代碼庫(kù)中的排序函數(shù)來(lái)解決這道題蛮浑。
示例:
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
進(jìn)階：
一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法。
首先只嚣，迭代計(jì)算出0沮稚、1 和 2 元素的個(gè)數(shù)，然后按照0册舞、1蕴掏、2的排序，重寫(xiě)當(dāng)前數(shù)組调鲸。
你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎盛杰？
題目難度
中等
分析
需要對(duì)0,1,2的元素進(jìn)行排序，把等于2的元素設(shè)置到末尾线得，再對(duì)剩下的元素進(jìn)行排序,把對(duì)三個(gè)元素排序的問(wèn)題轉(zhuǎn)化為對(duì)兩個(gè)元素的排序的問(wèn)題饶唤。
對(duì)兩個(gè)元素進(jìn)行排序的問(wèn)題可以使用快速排序的劃分算法。
具體的做法是：使用雙指針贯钩，一個(gè)指針從0開(kāi)始，指向元素為0的區(qū)域,一個(gè)指針從數(shù)組尾部開(kāi)始，指向元素為2的區(qū)域,遍歷元素角雷，如果等于2,設(shè)置到末尾祸穷，如果為0,設(shè)置到開(kāi)頭。
代碼
class Solution {
public:
void sortColors(vector<int>& nums) {
int begin = -1;
int end = nums.size();
for(int i = 0; i < end;) {
if(nums[i] == 0) {
++begin;
if(begin != end) {
swap(nums[begin] , nums[i]);
}
i++;
} else if(nums[i] == 2) {
--end;
if(end != i) {
swap(nums[end] , nums[i]);
}
} else {
i++;
}
}
}
};
