荷兰国旗问题 荷兰国旗问题算法

荷兰国旗问题:设有一个仅由红、白、兰这三种颜色的条块组成的条块序列。请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、兰的顺序排好,即排成荷兰国旗图案。

实现下列函数:
荷兰国旗问题 荷兰国旗问题算法
void HFlag(FlagList &f)

"荷兰国旗"的顺序表的类型FlagList定义如下:
#define red '0'
#define white '1'
#define blue '2'

typedef char ColorType;

typedef struct {
ColorType r[MAX_LENGTH+1];
intlength;
} FlagList;

其实描述起来很简单。给你一个数组,其中有0,1,2这三个数字。如何在一次遍历的前提下把这三种数字归类分组。比如

输入1 0 2 1 0 0 1 2 2 1 0 2,输出0 0 0 0 1 1 1 1 2 2 2 2。

void HFlag(FlagList &f)
{
inti=0;
char *pRed =&f.r[0];
char *pBlue= &f.r[f.length-1];
while(i<f.length)
{
if( f.r[i] == red )
{
char cTemp = *pRed;
*pRed = f.r[i];
f.r[i] = cTemp;
pRed++;

}
if( f.r[i] == blue )
{
char cTemp = *pBlue;
*pBlue = f.r[i];
f.r[i] = cTemp;
pBlue--;
}
if( f.r[i] == white )
{
i++;
}
if( &f.r[i] > pBlue )
break;
}
}

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/352262.html

更多阅读

背包问题算法 背包问题递归

0/1背包问题 1. 问题描述 给定一个载重量为m,n个物品,其重量为wi,价值为vi,1<=i<=n,要求:把物品装入背包,并使包内物品价值最大 2. 问题分析 在0/1背包问题中,物体或者被装入背包,或者不被装入背包,只有两种选择。 循环变量i,j意义:前i个物品能

Cognos问题集合 集合划分问题算法

1、Cognos不能使用Excel打开解决方法一:1.打开IE浏览器,在工具条中找到工具栏--àIntenet选项-à安全--à受信任的站点2.点击站点,添加可信任站点http://localhost:9080/p2pd/servlet/dispatch注意:对该区域中的所有站点要求服务器验

转载 德国奶粉,荷兰奶粉,哪个更好? 牛奶和奶粉哪个更好

原文地址:德国奶粉,荷兰奶粉,哪个更好?作者:这一站欧洲最近一个将要做妈咪的好友小梅,一直很纠结德国爱他美和荷兰奶粉,究竟哪个好的问题。小梅在网上看了一篇报道,传说德国爱他美是全球最顶尖的奶粉。准妈咪的心情,十分理解。这里,我们不讨

声明:《荷兰国旗问题 荷兰国旗问题算法》为网友走死在岁月里分享!如侵犯到您的合法权益请联系我们删除