求效率最高两数组交集方法

chunbin0220 发布于 2012/08/03 11:06
阅读 1K+
收藏 0

int a[],int b[]

a,b为不重复,未排序int数组

加载中
0
中山野鬼
中山野鬼

把长数组的数据依次丢入短数组中做比较。如果有重复的,则属于交集的元素,从短数组中剔除。基本上就这样了。

可以考虑,短数组每删除一定数量后,对数据进行压缩,将剔除掉数据的空位给挤出,以降低后续长数组的元素访问的内容。

由于你A,B里面的内容不重复,所以排序是没必要的。

0
CoserSeu
CoserSeu

用bitmap方法,一个数用两位bit表示,用一个bit数组表示某一数字是否出现过,初始化为全0,第一次遍历a数组,将数组中相应数字为下标的bit位设置为01,第二次遍历b数组,将数组中相应数字下标的bit位改变,如原为00的变为01,原为01的变为10。

到最后,遍历一遍bit数组,出现10位的对应的就是交集对应的数字

CoserSeu
CoserSeu
没错,主要看数据类型,数据类型比较大的话就比较难办。 这个唯一的好处在于消耗的空间是固定的,时间为O(n)
中山野鬼
中山野鬼
回复 @CoserSeu : 如果A,B数组分别是100万和1000万。而无论哪个数组,都是64位的整型。貌似你的BITMAP超级大吧。
CoserSeu
CoserSeu
时间复杂度为O(n),空间代价为n/16
0
canghailan
canghailan
确定一个数是否在集合中最快的是Hash吧。对小数组Hash,遍历长数组查询。
0
z
zippon
内存够用的话,显然hash么。
0
中山野鬼
中山野鬼

引用来自“canghailan”的答案

确定一个数是否在集合中最快的是Hash吧。对小数组Hash,遍历长数组查询。
小数组如果大,自身会有一定碰撞可能。同时hash的自身计算,大家要考虑一下。很多人喜欢用O(N)这些来分析计算量,这个本身没错。但如果工程经验不足,会对每次的计算费用有所忽略。hash是个不错的方法。不过我个人有点抵触。因为操作模式太过于复杂。其实最终可能更慢。
mahone
mahone
很多人喜欢用O(N)这些来分析计算量,这个本身没错。但如果工程经验不足,会对每次的计算费用有所忽略 这句话说的不错啊。。。我一直觉得hash的计算消耗,应该还是有点客观的。。。但是算O什么的时候,大家都直接忽略。。。
canghailan
canghailan
恩,的确。我看到这个题目的第一想法是小数组排序,二分搜索,有成熟的程序库支持,效率也不差。
0
Yisen
Yisen

@CoserSeu 的方法就很好了,占用空间不算大,效率也高

0
剑尖血凝紫
剑尖血凝紫

引用来自“CoserSeu”的答案

用bitmap方法,一个数用两位bit表示,用一个bit数组表示某一数字是否出现过,初始化为全0,第一次遍历a数组,将数组中相应数字为下标的bit位设置为01,第二次遍历b数组,将数组中相应数字下标的bit位改变,如原为00的变为01,原为01的变为10。

到最后,遍历一遍bit数组,出现10位的对应的就是交集对应的数字

假设是int数组,你设置完bitmap后,那要扫描2^32次

0
剑尖血凝紫
剑尖血凝紫

大数组m和小数组n各保存到一个bitmap中,一位表示一个整数是否在数值中,

遍历小数组的时候,直接检查大数组的对应位是否为1.

时间复杂度o(m+n), 

 

===================

不对,占用空间太大

想了想是不是 对大数组排序,再去遍历小数组去做大数组的二分查找 会好一点

小郭一号
小郭一号
对小数组排序更好
返回顶部
顶部