荷兰国旗问题
2018-11-11 本文已影响0人
小码弟
给定一个数组,元素只有三种取值:0, 1, 2。分别代表三种颜色红白蓝。设计函数调整数组,使得数组按照0,1,2 的顺序排列。
如:给定[1, 2, 2, 0,0, 1], 调整后[0,0,1,1,2,2]
思路:设置三个指针,zero指向所有0的右边界,one充当工作指针并跳过1的元素,two指向所有2的左边界
void sortColors(int* colors, int len)
{
if(len == 1)
return ;
int zeros = -1, one = 0, two = len;
while(one < two)
{
if(colors[one] == 0)
swap(colors, ++zeros, one++);
else
if(colors[one] == 2)
swap(colors, one, --two); // 这里one不能自加,
//因为原来two位置的元素不知道是不是1,one不动,接受下一轮检查
else
one++;
}
}