首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

合并算法,使得它的复杂度降低到一阶

2012-03-27 
求一个合并算法,使得它的复杂度降低到一阶我现在有n个解,每个解都是由0,1组成的向量.比如:(1,1,1,0,0,0,0,

求一个合并算法,使得它的复杂度降低到一阶
我现在有n个解,每个解都是由0,1组成的向量.比如:(1,1,1,0,0,0,0,0,1,1,1)
我规定前5个数字为一组,后三个数字为一组,再紧接着后面两个为一组,最后一个数字为一组.我想通过一个复杂度为n的线性时间,把这n个解中每一组里1的个数相同的解视为同解,再把这些不相同的解保存起来的算法.如:(1,1,0,0,1,0,0,1,1,0,0)和(0,0,1,1,1,1,0,0,0,1,0)为同种解,合并后解为(3,1,1,0).合并的解实际上就是把每一组里有多少1存了起来.

请高手赐教!在线等

[解决办法]
每组数字求和不就可以?1的个数就等于其和啊?
[解决办法]
(1,1,1,0,0--,0,0,0,--1,1--,1)
记数排序法
前面5位数有5个0、4个0、3个0。。。0个0共6种情况。接着3位有4种。。。3种,2种。共有6*4*3*2=144种。
建立144个元素的数组,清0,然后遍历N个向量,将对应值加1。OVER
[解决办法]
你的源数据时什么表示方式

最后得到的数据又是什么表示方式

比如

(1,1,0,0,1,0,0,1,1,0,0)
(0,0,1,1,1,1,0,0,0,1,0)
(0,0,1,1,1,1,0,0,0,1,1)
(0,0,1,1,1,1,0,0,0,1,1)
(0,0,1,1,1,1,0,0,0,0,0)

你的源数据是怎么样表示的


int[5][11] ???

然后你想得到的结果是什么样的



热点排行