有点意思的集合算法题,谁来挑战一下

little_kid 发布于 2015/09/07 20:34
阅读 311
收藏 1

有点意思的集合算法题;不是特别简单,也不是特别复杂,想做好还得好好想想。



源地址:http://www.gsymy.com/2015/09/07/get_subset_order.html

加载中
0
WENTX
WENTX
1.定义一个map把所有集合中的元素放入string类型的key中,这样放完之后,这个map中的所有key值的集合就是合并前那些集合的并集了,并且排好了序,这样的话,这个算法在实现上算是虽简单的吧,想听听楼主的思路。
2.第二个题目的意思是找出并集当中每个元素在他自己子集中的位置吗?
zhiguo-1
zhiguo-1
发布一下 我了去
0
little_kid
little_kid

我把题目再重新发一下


set1 = {"abc","bcd",...};
 
...
 
setn = {...}
 
1. 求所有集合的并集UnionSet
2. 将集合UnionSet中元素顺序进行编号,求出每个子集中元素的编号;
3. 选取Unionset中任意个元素,组成新的集合,求原有子集中哪些是新集合的子集(2015-09-08补充)

编程对于给定的集合以最小的时间代价完成12


题目3 有兴趣思考一下吗?

0
little_kid
little_kid
好方法,我看看
0
little_kid
little_kid

引用来自“WENTX”的评论

1.定义一个map把所有集合中的元素放入string类型的key中,这样放完之后,这个map中的所有key值的集合就是合并前那些集合的并集了,并且排好了序,这样的话,这个算法在实现上算是虽简单的吧,想听听楼主的思路。
2.第二个题目的意思是找出并集当中每个元素在他自己子集中的位置吗?

我说一下我的想法;

1. 用map来做并集是思路是可行的。但是用std::map效率不高,还有很大空间。

数据量稍微一大,std::map的插入会变慢;据说std::map是基于平衡树的,效率是O( log(N) )

的,所以用hashmap的话效率会高于std::map,那么这里就要用一个效率比较高的

hashmap 。关于hash算法的探究也算是一个话题;

2. 将std::string放入map之后效率也会降低,直接用char* 

3. 题目2中没有要求集合元素是有序的,而用std::map完成之后是有序的;这不是重点。

重点是集合中顺序,如果已经有序了,可以将每个子集里的元素指针做二分查找(如果用char*的话)算是比较快的一种方法;如果是无序的需要做循环遍历;这都不是很好的方法。

我能想到更好的方法是在题目1,插入数据时,将数据所在子集的指针作为最终并集中元素的一个成员变量(链表),这样最终产生并集后:

idx = 0

for (element in unionset)

{

   for (setPtr in element.setPtrs)

 {     setPtr[element].idx = idx;}

idx++;

}

我的想法你看怎么样?


little_kid
little_kid
回复 @WENTX : 有兴趣的话继续思考一下题目3
WENTX
WENTX
效率上确实需要注意一下,楼主考虑很全面,的想法不错。
0
little_kid
little_kid
源连接正文中我又补充了问题3
返回顶部
顶部