免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 求一个集合是否是另外一个集合的子集
最近访问板块 发新帖
查看: 4551 | 回复: 9
打印 上一主题 下一主题

[算法] 求一个集合是否是另外一个集合的子集 [复制链接]

麦哥哥

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2010-12-16 14:21 |只看该作者 |倒序浏览
函数声明为:int  IsSubset(int *pSetA, int nSetA_len, int *pSetB, int nSetB_len);判断A是否是集合B的子集
大家有没有比较有效率的算法。都来发表发表意见
luguo2050

论坛徽章:
0
2楼 [报告]
发表于 2010-12-16 14:29 |只看该作者
hash后比较
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
麦哥哥

论坛徽章:
0
3楼 [报告]
发表于 2010-12-16 14:38 |只看该作者
问题不知道B集合里的数，可能很大，那开辟的空间岂不很大么，hash是简单，o(n+m)的时间复杂度
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
麦哥哥

论坛徽章:
0
4楼 [报告]
发表于 2010-12-16 14:39 |只看该作者
hash是简单
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
麦哥哥

论坛徽章:
0
5楼 [报告]
发表于 2010-12-16 14:41 |只看该作者
可是不能确定要开辟多大空间啊，集合里的元素可能值很大
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
jerryz920

论坛徽章:
0
6楼 [报告]
发表于 2010-12-16 14:44 |只看该作者
排序二分，简单粗暴……
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
samlumengjun

论坛徽章:
0
7楼 [报告]
发表于 2010-12-16 15:19 |只看该作者
可以这样考虑,对集合a和集合b各自求积,然后用b的积对a的积求模,如果模为0,那么b就包含a,否则不包含,当然这两个集合的积至少要在64位整型的范围内,超过的话要自己作处理.另外就是要把负数做处理,全部转成正的.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
samlumengjun

论坛徽章:
0
8楼 [报告]
发表于 2010-12-16 15:23 |只看该作者
上面忘记了一条,要两边都去掉元素0,另外还可以在对b求积的时候做优化.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
starwing83

论坛徽章:
5
狮子座 日期:2013-08-20 10:12:24午马 日期:2013-11-23 18:04:102015年辞旧岁徽章 日期:2015-03-03 16:54:152015亚冠之德黑兰石油 日期:2015-06-29 18:11:1115-16赛季CBA联赛之新疆 日期:2024-02-21 10:00:53
9楼 [报告]
发表于 2010-12-16 15:39 |只看该作者
hash，或者基排再顺次，都是O(n)的。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
麦哥哥

论坛徽章:
0
10楼 [报告]
发表于 2010-12-18 23:14 |只看该作者
还有没其他好的方法呢？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP