|
锁定老帖子 主题：一道算法面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-03-16
...这个主题太有魅力了，多少兄弟的处女帖留这了。
set和数组的内存占用的差距大么？ |
| 返回顶楼 | |
|
发表时间：2010-03-16
很简单一道题，
改个参数吧，1000亿的两批数据。 |
| 返回顶楼 | |
|
发表时间：2010-03-16
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的数组？ |
| 返回顶楼 | |
|
发表时间：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亿左右才够..... |
| 返回顶楼 | |
|
发表时间：2010-03-16
貌似是20亿
|
| 返回顶楼 | |
|
发表时间：2010-03-16
先把其中一个数组的内容add()到一个集合里(list1).
然后把第二个数组中的元素也add()到这个集合里(list1). 第二次add()时候先用contains()判断是否重复,如果重复，add()到另一个集合里(list2). list2就是交集。。。。。 我遇到过这样的面试题。。就是这么做的 |
| 返回顶楼 | |
|
发表时间：2010-03-16
lyw985 写道 貌似是20亿
21 4748 3647 是的... |
| 返回顶楼 | |
|
发表时间：2010-03-16
最后修改：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的数组？ 
没想到啊，我刚才试了下，最多只能创建长度为 15465465 的int数组。这个和机器内存有关系，还是和jvm有关系？ |
| 返回顶楼 | |
|
发表时间：2010-03-16
数据(数组)应该是保存在磁盘文件上的，题目本身就有问题。
|
| 返回顶楼 | |
|
发表时间：2010-03-16
最后修改：2010-03-16
如果和JVM有关系的话，数组最大长度只能是1500多w了，两个1000W的数组内存就不够用了，估计没那俩数组一个近1000W数量级个数元素集合也不够用。
|
| 返回顶楼 | |
