一道算法面试题

有烟没火 · 发表于 2011-8-24 11:22

两个1000W个元素的数组，如何有效的找出他们的交集。

天上智喜 · 发表于 2011-8-24 11:22

元素是整数？还是任意对象？

shmilyyu · 发表于 2011-8-24 11:22

vieri122 写道
元素是整数？还是任意对象？

为整数

走就走吧 · 发表于 2011-8-24 11:23

我的思路是开一个长度为n的数组x。遍历第一个1000W个元素的数组a，对于每一个值a[i]，置x中相应的位为1，即x[a[i]]=1。再遍历第二个1000W个元素的数组b，对于每一个值b[i]，判断x[b[i]]是否为1，为1则该值属于交集。

至于开多少长度的数组，若题目中指定元素为整数，则n=Integer.MAX_VALUE，若元素为长整数，则n=Long.MAX_VALUE，若不知道范围，ok，遍历一遍x取最大值呗。

最后的时间复杂度都是O(n).

不知道各位TX有没有更好的解题思路~

已经来了吗 · 发表于 2011-8-24 11:23

对第一个1000W数组hash，生成一个hash化数组。对第二个1000W数组采取同样算法hash，得到下标i，取hash[i]是否为null，不为null则是交集。剩余的问题是如何解决hash冲突

月上萧萧 · 发表于 2011-8-24 11:23

整数的话，排序后比较好不好啊

醉倚西风 · 发表于 2011-8-24 11:24

开个数据池吧

帐号		自动登录	找回密码
密码			成为会员