題目
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
分析
這題看似簡(jiǎn)單绣否，但是在單次掃描的條件下渊啰，需要注意很多細(xì)節(jié)颅痊。
思路是設(shè)置雙指針践叠，分別表示red的末尾和blue的開(kāi)頭票髓，從而將整個(gè)數(shù)組分成三段陨享。
實(shí)現(xiàn)
class Solution {
public:
void sortColors(vector<int>& nums) {
int N=nums.size();
int red=0, blue=N-1;
for(int i=0; i<=blue;){
if(nums[i]==0)
swap(nums[i++], nums[red++]);
else if(nums[i]==2)
swap(nums[i], nums[blue--]);
else
i++;
}
}
};
思考
這題據(jù)說(shuō)可以用partition配合bind1st來(lái)實(shí)現(xiàn) 有空可以了解下弱卡。
