一个大数据 的算法，求思路。

一、两个整数数组各100亿条数据，已经排序，保存在磁盘上；内存10M， 
1.如何取得交集？时间和空间效率分别是多少？ 
2.如果其中一个数组只有100条数据，如何优化算法取得交集？时间和空间效率分别是多少？ 

7 个解决方案

#1

用类似归并排序的方法吧，2个文件各扫描一次。
第2种似乎可以采用类似对半查找。

#2

第一种时间复杂度是O(n),辅助空间的复杂度是常数O(1)
第二种时间复杂度O(log n),空间复杂度O(1)

#3

我想到个方法，租台超级计算机

#4

难道我理解错了？

既然两个数组A,B都已经排序，那么分别取出各自的最小值和最大值，即可得到交集范围
然后分段取出比较
如果 A[i]>B[j] 则j++
如果 A[i]<B(j) 则i++
如果 A[i]=B(j) 则 ==>交集数，i++,j++

一次扫描就可以

#5

引用 4 楼 worldy 的回复:

难道我理解错了？

既然两个数组A,B都已经排序，那么分别取出各自的最小值和最大值，即可得到交集范围
然后分段取出比较
如果 A[i]>B[j] 则j++
如果 A[i]<B(j) 则i++
如果 A[i]=B(j) 则 ==>交集数，i++,j++

一次扫描就可以

这个想法不错，学习了

#6

第一个问题：
    无论如何肯定要扫描一遍两个数组。A B两个数组根据大小移动指针。
    A[i]<B[j] i++;
    A[i]==B[j] temp[p] = A[i]; i++;j++;
    A[i]>B[j] j++;

第二个问题可以先二分查找，然后回到第一个问题。

#7

一楼写得精辟...4.5楼没看懂·····