arrays - 算法:将 2 个数组划分为 "only in A"、 "intersection of A & B"和 "only in B"

Question

我遇到这样一种情况，我有两个数组，我需要对它们进行分区，以便最终得到 3 个数组:

• 只在A中的元素
• 只在B中的元素
• 同时存在于A和B中的元素

例子:

A = [1, 4, 3, 2]
B = [2, 6, 5, 3]
3part(A,B) => [[1,4], [6,5], [2,3]] # the order of the elements in each array doesn't matter

我想出了一个正确的解决方案，但想知道它是否可以更快。它是(伪代码):

3part(A,B) =>
    a_only = []
    b_only = []
    intersect = []

    foreach a in A
        if B.contains(a)
            intersect.push(a)
        else
            a_only.push(a)

    foreach b in B
        if not intersect.contains(b)
            b_only.push(b)

    return [a_only, b_only, intersect]

在我手头的例子中，A 和 B 将各自包含多达 5000 个复杂结构(而不​​是整数)，并且它运行大约 1.5 秒。它被用作经常发生的用户交互的一部分，因此理想情况下它需要 <.5 秒。

顺便说一句，除了“差分-差分-交集”之外，这个操作是否有一个整体的名称？

谢谢!

编辑:

根据使用散列的建议，我更新后的代码运行时间不到 40 毫秒 :-D

伪代码如下:

(假设“key”是我用来比较的元素)

array_to_hash(A, Key)
    h = {}
    foreach a in A
        h[a[Key]] = a
    return h

3part(A,B) =>
    a_only = []
    b_only = []
    intersect = {} // note this is now a hash instead of array

    Ah = array_to_hash(A, 'key')
    Bh = array_to_hash(B, 'key')

    foreach ak in Ah.keys()
        if Bh.hasKey(ak)
            intersect[ak] = Ah[ak]
        else
            a_only.push(Ah[ak])

    foreach bk in Bh.keys()
        if not intersect.hasKey(bk)
            b_only.push(Bh[bk])

    return [a_only, b_only, intersect.values]

谢谢大家的建议。

Answer 1

如果你的数组是可排序的，那么你可以做两件事

1. 要检查一个值是否在另一个数组中，只需对另一个数组进行二进制搜索，复杂度 O(nlogm + mlogn)

2. 或者您可以使用 2 个指针将数组合并到 3 个数组中，因为数组已排序，如果第一个元素相等，则将它们添加到交集，否则如果 A 中的元素 < B 中的元素. 将 A 中的元素添加到数组 a[] 中，然后检查第二个元素与 B 中的第一个元素。
   如果 B 小于 A，则相同
   复杂度 O(n + m)。您可以使用 2 个指针维护我们指的是哪个元素