题意：
一个数组只可能含有3种数据，分别为1,2,3，请将数组排序（只能扫一遍）。
思路：
如果扫两遍的话，用个桶记录一下，再赋值上去就行了。
class Solution {
public:
void sortColors(vector<int>& nums) {
int cnt[]={};
for(int i=; i<nums.size(); i++)
cnt[nums[i]]++;
for(int j=,i=; j<; j++)
while(cnt[j]-- > )
nums[i++]=j;
}
};
AC代码
还有这种傻瓜方法，扫一遍先将2移到末尾，再扫一遍将0移到前面。仍然无效率。
class Solution {
public:
void sortColors(vector<int>& nums) {
int L=, R=nums.size()-;
for(int i=; i<nums.size(); i++)
{
while(L<R && nums[L]!=) L++;
while(L<R && nums[R]==) R--;
if(L<R) swap(nums[L],nums[R]);
}
L=, R=nums.size()-;
for(int i=; i<nums.size(); i++)
{
while(L<R && nums[L]!=) L++;
while(L<R && nums[R]!=) R--;
if(L<R) swap(nums[L],nums[R]);
}
}
};
AC代码
还有一种吊吊的，扫一遍就搞定的。扫一遍数组，考虑nums[i]，如果nums[i]=2，立刻换到末尾，此时nums[i]有可能仍然是2，如果是2，一直继续换到末尾。这样就保证了区间(L,i)中不可能出现2，如果此时nums[i]为0，就与前面的换，此时nums[i]就只可能是0或1了，0就一直换，1就pass。
class Solution {
public:
void sortColors(vector<int>& nums) {
int L=-, R=nums.size();
for(int i=; i<R; i++)
{
while(i<R&&nums[i]==)
swap(nums[i],nums[--R]);
if(nums[i]==)
swap(nums[i],nums[++L]);
}
}
};
AC代码
