找到两个排序数组的交集,在某些情况下需要少于O(m + n)个比较

Question

这是在两个数组的O(m+n)位置m和n长度中执行此操作的一种方法:

import random

def comm_seq(arr_1, arr_2):
    if len(arr_1) == 0 or len(arr_2) == 0:
        return []

    m = len(arr_1) - 1
    n = len(arr_2) - 1

    if arr_1[m] == arr_2[n]:
        return comm_seq(arr_1[:-1], arr_2[:-1]) + [arr_1[m]]

    elif arr_1[m] < arr_2[n]:
        return comm_seq(arr_1, arr_2[:-1])

    elif arr_1[m] > arr_2[n]:
        return comm_seq(arr_1[:-1], arr_2)


if __name__ == "__main__":
    arr_1 = [random.randrange(0,5) for _ in xrange(10)]
    arr_2 = [random.randrange(0,5) for _ in xrange(10)]
    arr_1.sort()
    arr_2.sort()
    print comm_seq(arr_1, arr_2)

有些技术在某些情况下使用的O(m+n)比较少吗？例如:arr_1=[1,2,2,2,2,2,2,2,2,2,2,100]和arr_2=[1,3,100]

(不寻找哈希表实现)

Answer 1

二进制搜索算法需要O(logm)时间来查找长度为m的数组中的数字.因此,如果我们从长度为m的数组中搜索长度为n的数组的每个数字,则其总体时间复杂度为O(nlogm).如果m远大于n,O(nlogm)则实际上小于nO(m+n).因此,在这种情况下,我们可以基于二分搜索实现一种新的更好的解决方案.资源

然而,这并不一定意味着二元搜索比O(m + n)情况更好.实际上,当n << m(n与m相比非常小)时,二分搜索方法才更好.

Answer 2

据我所知,有几种不同的方法可以解决这个问题,但没有一种比O(m + n)好.我不知道你怎么能有比这更快的算法(除了奇怪的量子计算答案),因为你必须比较两个数组中的所有元素,否则你可能会错过重复.

暴力 使用两个嵌套的for循环.从第一个数组中取出每个元素,并在第二个数组中进行线性搜索.O(M*N)时间,O(1)空间

地图查找 使用查找结构,如哈希表或二叉搜索树.将所有第一个数组放入地图结构中,然后遍历所有第二个数组并查找地图中的每个元素以查看它是否存在.无论数组是否排序,这都有效.二进制搜索树时间的O(M*log(M)+ N*log(M))或Hashtable的O(M + N)时间都是O(M)空间.

二进制搜索 像蛮力一样,但是从第一个数组中获取每个元素,并在第二个数组中搜索它. O(m*log(N))时间,O(1)空间

Parallel Walk 就像合并排序的合并部分.从每个数组的前面开始有两个指针.比较这两个元素,如果它们相等则存储副本,否则将指针移动到较小的值一个点并重复直到你到达其中一个数组的末尾.O(M + N)时间,O(1)空间

无论如何,您必须检查两个数组中的每个元素,否则您将不知道是否找到了所有重复项.你可以争论边缘情况,其中一个数组更大或更小,但这不适用于你考虑所有输入范围的算法.