【算法习作】荷兰国旗问题-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

【算法习作】荷兰国旗问题

简介:

1.问题描述:

   

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

2.问题分析:

这个问题我们可以将这个问题视为一个数组排序问题,这个数组分为前部,中部和后部三个部分,每一个元素(红白蓝分别对应0、1、2)必属于其中之一。由于红、白、蓝三色小球数量并不一定相同,所以这个三个区域不一定是等分的,也就是说如果我们将整个区域放在[0,1]的区域里,由于三色小球之间数量的比不同(此处假设1:2:2),可能前部为[0,0.2),中部为[0.2,0.6),后部为[0.6,1]。我们的思路如下:将前部和后部各排在数组的前边和后边,中部自然就排好了。具体的:

设置两个标志位begin和end分别指向这个数组的开始和末尾,然后用一个标志位current从头开始进行遍历:

1)若遍历到的位置为0,则说明它一定属于前部,于是就和begin位置进行交换,然后current向前进,begin也向前进(表示前边的已经都排好了)。

2)若遍历到的位置为1,则说明它一定属于中部,根据总思路,中部的我们都不动,然后current向前进。

3)若遍历到的位置为2,则说明它一定属于后部,于是就和end位置进行交换,由于交换完毕后current指向的可能是属于前部的,若此时current前进则会导致该位置不能被交换到前部,所以此时current不前进。而同1),end向后退1。

3.解决代码:

 




本文转自gnuhpc博客园博客,原文链接http://www.cnblogs.com/gnuhpc/archive/2012/12/21/2828166.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章