当前位置:   article > 正文

红蓝白三色球的排列,红色居前,白色居中,蓝色居后,算法设计,每个球只能查看一次_设有顺序放置的n个盒子,每个盒子装有一个颜色小球,小球颜色为红白蓝

设有顺序放置的n个盒子,每个盒子装有一个颜色小球,小球颜色为红白蓝

题目:

设有顺序放置n个球,每个球的颜色是红,白,蓝之一。要求重新安排这些球,使得所有红色的球在前,所有白色球居中,所有蓝色的球居后。重新安排时,对每种球的颜色只能查看一次,并且只允许交换操作来调整位置。

算法思想:

O(n),三个指针夹逼。

对于题目的要求,每个球只能查看一次,并且只能交换操作。那么就是暗示我们用指针进行遍历比对。

i=0,j=n-1,k=i;

遍历的规则:

1.i遇到红色直接跳过,j遇到蓝色直接跳过。

2.红》白》蓝,那么当Si>Sj,直接交换即可。并且交换以后的只不为白色,就往中间走一步。

3.k跟着i走。

4.当i,j都为白色,就启用k,k代替i往中间夹逼,遇到蓝色与Sj交换,遇到红色与Si交换。

5.最后k>=j,就结束。

例子:

白    红    蓝    白      蓝    蓝    红      白      红

i k                                                                 j

显然Si<Sj那么交换得到:(并且非红色,则前进。)

红    红    蓝    白      蓝    蓝    红      白      白

        i k                                                         j

遇到红就跳,i++,k++:

红    红    蓝    白      蓝    蓝    红      白      白

                i k                                                j

以此类推就可以得到:

  红     红     红    蓝    蓝     蓝     白   白     白

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/744976
推荐阅读
相关标签
  

闽ICP备14008679号