面试算法~两个整数数组各100亿条数据

1、题目

 

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

---

 2、解题思路

 

最近换工作，见到这份面试题，说一说我的思路

对于第一个问题，是比较容易处理的，可以借助归并排序的思路来解，只是需要判断两边的数是否相等就可以了，时间效率是O(n)，空间复杂度是O(1)

复杂的是第二个小问题，100亿对100亿取交集时，可以借助归并排序的思路，但其中一个是100个元素时，这个问题就退化成了在1亿个有序元素中查找1个元素是否存在的问题，这种情况下应该使用二分查找

如果你想到了二分查找，我认为你已经接近答案了，接下来要注意的是，二分查找的范围

大数组的查找范围是可以不断缩小的，假设小数组为A，那么A[0]可以确定二分查找的起始位置，A[99]可以确定二分查找的结束位置，当查询A[1]时就可以借助A[0]和A[99]所确定的范围，查找A[98]时可以借助A[1]和A[99] 确定的范围

---

 

3、示例代码

 

#coding=utf-8

lst1 = [i for i in range(100)]
lst2 = [3,5,7,19]

'''
返回False,表示没有找到,同时返回下一次可以二分查找的起点
返回True,表示找到了,同时返回下一次可以二分查找的起点
'''
def binry_search(lst,target,start,end):
    if start > end:
        return False,end

    mid = (start + end)/2
    if target == lst[mid]:
        return True,mid
    elif target > lst[mid]:
        return binry_search(lst,target,mid+1,end)
    else:
        return binry_search(lst,target,start,mid-1)


def get_set(lst_big,lst_title):
    lst = []
    start = 0
    end = len(lst_big)-1

    t_start = 0
    t_end = len(lst_title)-1
    while t_start <= t_end:
        #从左边开始对小数组元素进行二分查找
        exist,index = binry_search(lst_big,lst_title[t_start],start,end)
        start = index
        t_start += 1
        if exist:
            lst.append(lst_big[index])

        # 从右边开始对小数组元素进行二分查找
        if t_start < t_end:
            exist,index = binry_search(lst_big,lst_title[t_end],start,end)
            end = index
            t_end -= 1
            if exist:
                lst.append(lst_big[index])



    return lst

print get_set(lst1,lst2)