荷兰国旗问题

╰+哭是因爲堅強的太久メ 2022-01-14 06:45 239阅读 0赞

刚才在严蔚敏的数据结构习题上看到的这个题。看了几篇博客。貌似都没有结合数据结构的意思来解释。

让我有种冲动写篇文章。。就把这当作我的第一篇博文吧。

问题描述：

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

解析：

**算法一：**

首先复杂度为O（n）。这很容易让人想到扫一遍然后放入3个栈中。这样空间复杂度就为O(3\*n)。

其实这种算法用到了基数排序的思想。先设置判断条件。把符合条件的放入相应栈中，然后按序取出。

虽然看上去算法不稳定。由于只有颜色这一种区分，所以取出的顺序可以随便取。

优点：

容易想到。实现不复杂，只用设置3个栈，并且标号就行了。

缺点：

空间浪费大。而实际上元素移动的次数为2n。比下面说到的方法要多。

**算法二：**

有了算法一，我们能不能缩小空间的使用呢？答案是可以。

因为简单一看。如果我们把栈设在原始的数组中的话。是不是就可以节约3n的空间了？

那么怎样把栈塞到原始数组中呢？其实只用多扫描一遍原始数组就可以了。记录下rflag wflag bflag的次数就可以了！

如此以来。3个flag变量就成了栈的top变量了！

然后开始扫描3个变量的位置，如果是对应相同，那么就自加。如果不是，就找当前位置的颜色放到对应的栈中。

比方说红色栈顶事蓝色。那么就和对应的bflag所处位置上元素交换。

然后再来判断栈顶元素。如果是红色。那么OK。如果是白色那么就继续交换。直到为红色为止。

如果满了的话就把wflag换成rflag的位置。那么就只和bflag交换了。

优点：

空间大幅减少。相对算法一的移动次数相对减少，大概是n样子（似乎再复杂的情况交换次数也是n，有兴趣的可以自己画画）。

缺点：

实现比较复杂。逻辑也相对前面的复杂一点。

**算法三：**

有了算法二，又没办法让2n次扫描变成n次呢？答案也是确定的~~~

假如我们只设置两个栈。一个红，一个蓝。那么我们遇到蓝栈底就放到最右，红栈底放到最左。

再设置一个中间变量就OK了~

如何实现呢？

和算法二类似。红蓝两个栈顶都不是对应的红蓝。而是其他颜色。

设置中间变量来扫描数据。是红色，就放入红栈中。是蓝色就放入蓝栈中。

如果遇到白色就直接跳过吧~因为白色永远在中间，不可能入栈~

当bflag==中间变量&&中间变量所指向的地址值为白色，那么程序结束。

优点：

简单。实现方便。空间占用少。

缺点：  
仔细想想，如果要确定扫描次数，似乎也是2n。所以比较上不占优。

发表评论取消回复

表情：

评论列表（有 0 条评论，239人围观）

还没有评论，来说两句吧...

相关阅读

相关荷兰国旗问题

一、问题描述荷兰国旗问题，顾名思义，就是按照荷兰国旗的形式，给定一个数 x ，将 < x 的数放到左边，=x 的数放中间，>x 的数放右边，将数组中的元素分成三块，有的

小鱼儿/ 2023年01月16日 06:17/ 0 赞/ 134 阅读

相关题目268 荷南国旗问题

![20160729142714848][] 已AC代码： include<iostream> include<algorithm> using n

短命女/ 2022年09月24日 11:16/ 0 赞/ 61 阅读

相关从荷兰国旗问题到快排优化升级

如果在计算机领域存在一门技艺，放在十年、二十年后依然不过时，我想那必然是算法与数据结构。一、荷兰国旗问题 ![watermark_ty

偏执的太偏执、/ 2022年09月12日 05:47/ 0 赞/ 158 阅读

相关荷兰国旗问题

时间：2014.08.07 地点：基地 \-----------------------------------------------------------------

短命女/ 2022年08月10日 17:43/ 0 赞/ 142 阅读

相关荷兰国旗问题（Java）

需求：给一个数组arr，给一个数num，将数组中小于num的数放在左边，等于num的数放在中间，大于num的数全部放在右边。代码： import jav

客官°小女子只卖身不卖艺/ 2022年05月20日 08:22/ 0 赞/ 147 阅读

相关 acm 荷兰国旗问题

荷兰国旗问题时间限制：3000 ms | 内存限制：65535 KB 难度：1 输入第1行是一个正整数n（n<100），表示有n组测试数据。接下

墨蓝/ 2022年05月17日 12:23/ 0 赞/ 136 阅读

相关快排-荷兰国旗

在使用partition-exchange排序算法时，如快速排序算法，我们会遇到一些问题，比如重复元素太多，降低了效率，在每次递归中，左边部分是空的(没有元素比关键元素小)，而

系统管理员/ 2022年05月16日 06:52/ 0 赞/ 168 阅读

相关【算法】Python实现快速排序--荷兰国旗问题及奇偶数快速划分

文章目录一、序言二、”荷兰国旗难题“问题描述三、问题分析

骑猪看日落/ 2022年04月15日 05:59/ 0 赞/ 387 阅读

相关一文了解荷兰国旗问题

> 题目描述我们将乱序的红白蓝三色小球排列成有序的红白蓝三色同颜色在一起的小球组。这个问题之所以叫荷兰国旗，是因为我们将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国

叁歲伎倆/ 2022年02月13日 13:50/ 0 赞/ 220 阅读

相关荷兰国旗问题

刚才在严蔚敏的数据结构习题上看到的这个题。看了几篇博客。貌似都没有结合数据结构的意思来解释。让我有种冲动写篇文章。。就把这当作我的第一篇博文吧。问题描述：荷兰国旗问

╰+哭是因爲堅強的太久メ/ 2022年01月14日 06:45/ 0 赞/ 239 阅读