about 1 results (0.01 seconds)

面试题:求两个各有100亿数据的有序整型数组的交集

by LauCyun Jun 28,2017 15:23:42 31,223 views

最近朋友换工作,遇到这份面试题。

题目:

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

 

解题思路:

Q1:

二路归并法:既然两个数组A、B都已经排序,那么扫描一遍两个数组即可。A、B两个数组根据大小移动指针:

  • 如果 A[i]>B[j],则 j++
  • 如果 A[i]<B[j],则 i++
  • 如果 A[i]=B[j],则就是交集数,i++ j++

所以时间效率为\(O(n)\),空辅助空间的复杂度为\(O(1)\)

Q2:

100亿对100亿取交集时,可以借助归并排序的思路,但其中一个是100个元素时,这个问题就退化成了在1亿个有序元素中查找1个元素是否存在的问题。

在这种情况下,可以考虑使用二分查找法。先遍历长度较小的数组,然后将这个元素值在长度较大的数组中进行二分查找。 

所以时间复杂度为\(O(nlogn)\),空辅助空间的复杂度为\(O(1)\)

 

算法实现:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

import random


class Sort:
    def mergeSort(self, alist):
        if len(alist) <= 1:
            return alist

        mid = int(len(alist) / 2)
        left = self.mergeSort(alist[:mid])
        right = self.mergeSort(alist[mid:])
        return self.mergeSortedlst(left, right)

    # @param A and B: sorted integer lst A and B.
    # @return: A new sorted integer lst
    def mergeSortedlst(self, A, B):
        sortedlst = []
        l = 0
        r = 0
        while l < len(A) and r < len(B):
            if A[l] < B[r]:
                sortedlst.append(A[l])
                l += 1
            else:
                sortedlst.append(B[r])
                r += 1
        sortedlst += A[l:]
        sortedlst += B[r:]

        return sortedlst


def intersection(lst1, lst2):
    """
        Intersection of lst1 and lst2.
    :param lst1: lst1
    :param lst2: lst2
    :return: 
    """
    lst_tmp = []
    i, j = 0, 0
    while i < len(lst1) and j < len(lst2):
        if lst1[i] > lst2[j]:
            j += 1
        elif lst1[i] < lst2[j]:
            i += 1
        else:
            lst_tmp.append(lst1[i])
            i += 1
            j += 1
    return lst_tmp


def binary_search(lst, target):
    """
        Binary search.
    :param lst: lst
    :param target: target value
    :return: index
    """
    if not lst:
        return -1

    start, end = 0, len(lst) - 1
    while start + 1 < end:
        mid = int((start + end) / 2)
        if lst[mid] == target:
            start = mid
        elif lst[mid] < target:
            start = mid
        else:
            end = mid

    if lst[start] == target:
        return start
    if lst[end] == target:
        return end
    return -1


if __name__ == '__main__':
    n = 100
    array1 = [random.randint(0, n) for i in range(n)]
    array1 = Sort().mergeSort(array1)
    array2 = [random.randint(0, n) for i in range(n)]
    array2 = Sort().mergeSort(array2)
    print("array1:", array1)
    print("array2:", array2)
    k = 10
    array3 = [array1[i] for i in range(0, n, int(n / k))]
    print("array3:", array3)


    def q1(lst1, lst2):
        return intersection(lst1, lst2)


    def q2(lst_big, lst_small):
        lst_tmp = []
        small_start, small_end = 0, len(lst_small) - 1
        while small_start <= small_end:
            # 从左边开始二分查找
            index = binary_search(lst_big, lst_small[small_start])
            if (index > -1) and (index < n):
                lst_tmp.append(lst_big[index])
            small_start += 1

            # 从右边开始二分查找
            if small_start < small_end:
                index = binary_search(lst_big, lst_small[small_end])
                if (index > -1) and (index < n):
                    lst_tmp.append(lst_big[index])
                small_end -= 1

        return lst_tmp


    print("Q1(Intersection of array1 and array2): ", q1(array1, array2))
    print("Q2(Intersection of array2 and array3): ", q2(array2, array3))

(全文完)

...

Tags Read More..