6

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

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]

（不寻找哈希表实现）

4

4 回答 4

5

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

然而，这并不一定意味着在 O(m+n) 的情况下二分查找比 O(m+n) 更好。事实上，只有当 n << m（n 与 m 相比，n 非常小）时，二分查找方法才更好。

于 2012-11-22T04:08:39.717 回答
5

据我所知，有几种不同的方法可以解决这个问题，但没有一个比 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) 空间

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

于 2012-11-22T04:23:52.790 回答
1

如果您使用单边和正常二分搜索的组合，则可以使用具有 O(N*log(M/N)) 比较的算法。在最坏的情况下（当两个数组大小相等时），这等于 O(N) = O(M + N) 比较。这里 M 是最大数组的大小，N 是较小数组中不同元素的数量。

获取两个数组中最小的一个，并在第二个数组中搜索它的每个元素。从单边二分搜索开始：尝试位置 M/N、2*M/N、4*M/N...，直到找到大于所需的元素。然后使用正常的二进制搜索来查找位置 0 和 2 k *M/N 之间的元素。

如果找到匹配元素，则使用单边和正常二分查找的相同组合来查找重复匹配元素的运行在哪里结束，并将适当数量的匹配元素复制到输出。您可以使用相同的二进制搜索组合来计算较小数组中重复元素的数量，并获取这些重复计数中的最小值以确定结果中应包含多少元素。

要继续处理较小数组中的下一个元素，请使用较大数组中的起始位置，上一步结束的位置。

于 2012-11-22T08:44:42.400 回答
1

您可以使用 hash_table 保存大数组，然后扫描另一个小数组以计算两个数组的交集。

import random

def comm_seq(arr_1, arr_2):
    if len(arr_1) < len(arr_2): arr_1, arr_2 = arr_2, arr_1
    cnt = {}
    for item in arr_1: 
        cnt.setdefault(item, 0)
        cnt[item] += 1
    # save the large array in a hash_table
    ret = []
    for item in arr_2:
        p = cnt.get(item, 0)
        if p: 
            ret.append(item):
            cnt[item] -= 1
    # scan the small array and get the answer
    return ret

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)

如果我们将 py 字典的复杂度视为 O(1)，则总复杂度为 O(min(n, m))

于 2012-11-22T04:19:05.470 回答