荷兰国旗问题

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++;
   }
}
上一篇 下一篇

猜你喜欢

热点阅读