|
锁定老帖子 主题：一道算法面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-03-16
最后修改：2010-03-16
robertliudeqiang 写道 数据(数组)应该是保存在磁盘文件上的，题目本身就有问题。
这楼编辑过了 确实是题目有问题 |
| 返回顶楼 | |
|
发表时间：2010-03-16
zhanghaocool 写道 robertliudeqiang 写道 数据(数组)应该是保存在磁盘文件上的，题目本身就有问题。
这楼编辑过了 确实是题目有问题 如果现实中需要呢? |
| 返回顶楼 | |
|
发表时间：2010-03-16
最后修改：2010-03-16
抛出异常的爱 写道 zhanghaocool 写道 robertliudeqiang 写道 数据(数组)应该是保存在磁盘文件上的，题目本身就有问题。
这楼编辑过了 确实是题目有问题 如果现实中需要呢? 问题没有想清楚，观望。 |
| 返回顶楼 | |
|
发表时间：2010-03-16
最后修改：2010-03-16
抛出异常的爱 写道 zhanghaocool 写道 robertliudeqiang 写道 数据(数组)应该是保存在磁盘文件上的，题目本身就有问题。
这楼编辑过了 确实是题目有问题 如果现实中需要呢? 我知道的太少了，让我想，按照这会得来的启示我就把数据存磁盘文件里，然后一点一点数据读着分析吧 |
| 返回顶楼 | |
|
发表时间：2010-03-16
抛出异常的爱 写道 more2051 写道 zhangchen 写道 e_man 写道 我的思路是开一个长度为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有没有更好的解题思路~ 正解！ 请问怎样定义一个长度超过Integer.MAX_VALUE的数组？ 1000W还不大于Integer.MAX_VALUE 2亿左右才够..... e_man的意思是若数组中元素有大于Integer.MAX_VALUE的时，n就大于Integer.MAX_VALUE。定义这样一个数组貌似行不通。 |
| 返回顶楼 | |
|
发表时间：2010-03-16
循环读取，判断是否相等，如果相等就添加到一个新数组当中。比较死
|
| 返回顶楼 | |
|
发表时间：2010-03-16
将第一个数组 存放在一个二叉树中，然后再将第二个数组的各数据依次加入到该树中，如果相等则将该节点flag标志为true，剩下的只需要读取二叉树了。
|
| 返回顶楼 | |
|
发表时间：2010-03-16
http://flysunsystem.iteye.com/blog/617579
看下我写得关于这方面的，不知道对不对。 |
| 返回顶楼 | |
|
发表时间：2010-03-17
zhanghaocool 写道 more2051 写道 zhangchen 写道 e_man 写道 我的思路是开一个长度为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有没有更好的解题思路~ 正解！ 请问怎样定义一个长度超过Integer.MAX_VALUE的数组？ 
没想到啊，我刚才试了下，最多只能创建长度为 15465465 的int数组。这个和机器内存有关系，还是和jvm有关系？ 创建byte数组就可以了，不需要创建int数组。 |
| 返回顶楼 | |
|
发表时间：2010-03-17
使用hash表，同一整数在hash表中的位置相同。
这种做法时间复杂度可以在O(n)，但要浪费空间。 |
| 返回顶楼 | |
