开发者社区> 老朱教授> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介:
+关注继续查看

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,如需转载请自行联系原作者

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

相关文章
verdaccio:搭建npm私有服务器--原来这么简单
verdaccio:搭建npm私有服务器--原来这么简单
186 0
PHP面试题:合并两个数组有几种方式,试比较它们的异同2
PHP面试题:合并两个数组有几种方式,试比较它们的异同2
30 0
DL之DNN:利用MultiLayerNet模型【6*100+ReLU+SGD,weight_decay】对Mnist数据集训练来抑制过拟合
DL之DNN:利用MultiLayerNet模型【6*100+ReLU+SGD,weight_decay】对Mnist数据集训练来抑制过拟合
43 0
《SEO的艺术(原书第2版)》——1.3 人类搜索的目标
本节书摘来自华章计算机《SEO的艺术(原书第2版)》一书中的第1章,第1.3节,作者:(美)恩吉(Enge, E.)著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1318 0
一步一步写算法(之挑选最大的n个数)
原文: 一步一步写算法(之挑选最大的n个数) 【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】     从一堆数据中挑选n个最大的数,这个问题是网上流传的比较广的几个问题之一。
787 0
Hash算法,及HashMap使用
为什么要Hash? 哈希表是基于数组实现的,哈希算法就是如何将键值(key)转换成数组小标的方法,哈希化可以提供非常高的操作(插入、删除、查询)效率,因为对有序数组的查询,即使是二分查找也只能做到O(logN),因为哈希可以直接将要查询的key转化为数组小标,所以可以达到O(1)的时间级。 Hash算法:将key做hash后的值叫hashcode,hashcode的值范围可能很大,
1258 0
+关注
3545
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载