美文网首页
荷兰国旗问题

荷兰国旗问题

作者: 小码弟 | 来源:发表于2018-11-11 19:17 被阅读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++;
   }
}

相关文章

  • sort-colors

    荷兰国旗问题

  • 荷兰国旗问题

    给定一个数组,元素只有三种取值:0, 1, 2。分别代表三种颜色红白蓝。设计函数调整数组,使得数组按照0,1,2 ...

  • 荷兰国旗问题

    荷兰国旗问题:给定一个数num,将数组中划分成3部分,小于num的部分,等于num的部分,大于num的部分 例题:...

  • 荷兰国旗问题

    1.荷兰国旗问题 传入num 数组中大于num的数放左边 小于num的数放右边 等于num的数 放中间 1....

  • 荷兰国旗问题

    荷兰国旗问题 1、问题 荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示: 假设这样的条纹有多条,且各种颜色的...

  • 【算法】快速排序及优化

    一、荷兰国旗问题 在讲快速排序前,我们先来看看荷兰国旗问题。题目如下: 其实,这就是快排的partition过程,...

  • 【数组】--荷兰国旗问题

    问题:现有红,白,蓝三个不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色球在一起。红白蓝...

  • 荷兰国旗问题(颜色排序问题)

    版权声明:本文为博主原创文章,转载请注明出处。个人博客地址:https://yangyuanlin.club欢迎来...

  • 算法—数组:荷兰国旗问题

    tips:本文章内容来自《程序员编程艺术:面试和算法心得》给定一个字符串里面只有"R" "G" "B" 三个字符,...

  • 9. 荷兰国旗问题

    题意:把n个红、白、蓝三种不同颜色的小球,乱序排列在一起,请通过两两交换任意两球的方式,使得从左到右小球的颜色依次...

网友评论

      本文标题:荷兰国旗问题

      本文链接:https://www.haomeiwen.com/subject/nqhffqtx.html