主题：求解名企校园招聘数据结构题
fancy412
[专家分：0] 发布于 2007-01-15 23:03:00
有A、B两个文件，文件格式相同，均为每行一个十进制整型数字，两个文件的行数不一定相等，但均在一千万行左右。A文件中的数字两两不等，B文件中的数字两两不等， 请用一个算法找出A和B两文件中所有相同的数，并且从小到大有序输出。
请考虑统计程序如何实现，给出设计思路和关键算法（可使用伪代码），并估计程序核心代码的时间复杂度和空间复杂度。
回复列表 （共9个回复）
沙发
argentmoon [专家分：13260] 发布于 2007-01-15 23:23:00
平衡二叉树或HASH吧。
板凳
DFDer [专家分：70] 发布于 2007-01-18 00:35:00
用A文件的数插入，用B文件的数查找
3 楼
orangelegend [专家分：860] 发布于 2007-01-19 22:39:00
一千万行，二叉平衡树要开多少的空间啊。
浪费多少指针结点。
估计不行
4 楼
orangelegend [专家分：860] 发布于 2007-01-19 22:41:00
这种东西肯定要涉及到
外部排序
动用硬盘或虚拟存储空间的
5 楼
argentmoon [专家分：13260] 发布于 2007-01-19 23:30:00
一千万并不多，一个int算4个字节，一千万才38多M
6 楼
ykwmz [专家分：150] 发布于 2007-01-27 16:27:00
A排序+B排序+Merge A,B(C)+遍历C
f = nlogn + mlogm + m + n + m + n = O(xlogx) (x = Max(n,m))
7 楼
fwjmath [专家分：80] 发布于 2007-01-30 21:00:00
刚看了看《编程珠玑》~~~第一个就是有关这个问题的~~~我写一下伪代码~~~
//init
for i=[1, maxint]
bit[i]=0
do
从A读入一个数n
bit[n]=1
loop until EOF(A)
do
从B读入一个数n
bit[n]++
loop until EOF(B)
for i=[1, maxint]
if bit[i]==2 then 输出i
end
在书中这种方法被称作位图方法~~~时间和空间复杂度都是O(n)~~~如果bit实现得好的话会很快很节省内存的~~~
8 楼
ykwmz [专家分：150] 发布于 2007-02-01 18:05:00
[quote]刚看了看《编程珠玑》~~~第一个就是有关这个问题的~~~我写一下伪代码~~~
//init
for i=[1, maxint]
bit[i]=0
do
从A读入一个数n
bit[n]=1
loop until EOF(A)
do
从B读入一个数n
bit[n]++
loop until EOF(B)
for i=[1, maxint]
if bit[i]==2 then 输出i
end
在书中这种方法被称作位图方法~~~时间和空间复杂度都是O(n)~~~如果bit实现得好的话会很快很节省内存的~~~[/quote]
楼上的这位仁兄~~不是我说你。。麻烦你在讲所谓的时间和空间复杂度的时候，先开个1000万的数组给大家看看。。。
9 楼
fwjmath [专家分：80] 发布于 2007-02-02 12:57:00
[quote][quote]刚看了看《编程珠玑》~~~第一个就是有关这个问题的~~~我写一下伪代码~~~
//init
for i=[1, maxint]
bit[i]=0
do
从A读入一个数n
bit[n]=1
loop until EOF(A)
do
从B读入一个数n
bit[n]++
loop until EOF(B)
for i=[1, maxint]
if bit[i]==2 then 输出i
end
在书中这种方法被称作位图方法~~~时间和空间复杂度都是O(n)~~~如果bit实现得好的话会很快很节省内存的~~~[/quote]
楼上的这位仁兄~~不是我说你。。麻烦你在讲所谓的时间和空间复杂度的时候，先开个1000万的数组给大家看看。。。[/quote]
1byte可以放4个我这里的bit的...折算一下30+MB也就可以了...如果你还是觉得太大的话可以分区间啊...变通一下很容易的...
我来回复
您所在位置：