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

我有一种情况，我有两个数组，我需要对它们进行分区，以便最终得到 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 秒。它被用作经常发生的用户交互的一部分，因此理想情况下它需要 顺便说一句，除了“差异-差异-交集”之外，这个操作是否有一个整体的名称？谢谢!编辑:根据使用散列的建议，我更新的代码在 40 毫秒内运行:-D这是伪代码:(说“key”是我用来比较的元素)array_to_hash(A, Key) h = {} foreach a in A h[a[Key]] = a return h3part(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]谢谢大家的建议。 最佳答案 我觉得你让自己受到原始操作假设的阻碍。当前的硬件包括出色的散列支持和 GEMM 操作。 将 A 和 B 的值散列到一个空间中，范围为 |A + B|。 将两个数组转换为该范围内的单热编码。 应用向量 AND-OR-NOT 运算来获得您的三个结果。关于arrays - 算法:将 2 个数组划分为 "only in A"、 "intersection of A & B"和 "only in B"，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45696880/