|
锁定老帖子 主题：一道算法面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-03-15
最后修改：2010-03-15
两个1000W个元素的数组，如何有效的找出他们的交集。
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2010-03-15
元素是整数？还是任意对象？
|
| 返回顶楼 | |
|
发表时间：2010-03-15
还真不会，解决方案呢？
|
| 返回顶楼 | |
|
发表时间：2010-03-16
vieri122 写道 元素是整数？还是任意对象？
为整数 |
| 返回顶楼 | |
|
发表时间：2010-03-16
排序+归并后再找如何
|
| 返回顶楼 | |
|
发表时间：2010-03-16
我的思路是开一个长度为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有没有更好的解题思路~ |
| 返回顶楼 | |
|
发表时间：2010-03-16
对第一个1000W数组hash，生成一个hash化数组。对第二个1000W数组采取同样算法hash，得到下标i，取hash[i]是否为null，不为null则是交集。剩余的问题是如何解决hash冲突
|
| 返回顶楼 | |
|
发表时间：2010-03-16
1000W？这个数据算是大数据了
一般的方法肯定要挂 |
| 返回顶楼 | |
|
发表时间：2010-03-16
整数的话，排序后比较好不好啊
|
| 返回顶楼 | |
|
发表时间：2010-03-16
开个数据池吧
|
| 返回顶楼 | |
