algorithm - 找到非重叠数组对的数量

Question

问题是从给定的一组数组中计算非重叠数组对的数量(计算所有数组对，使得它们没有任何共同元素)。

例如给定，

a = [1,2,3]
b = [2,3,4]
c = [6,7,8]
d = [7,10,20]

以下对不重叠(a,c), (a,d), (b,c), (b,d) 因为它们没有任何共同的元素，所以这个问题的答案是 4

我有一个 n^2 解决方案，它计算每个数组与每个其他数组的交集，如果交集为空集则递增计数。

有没有有效的方法来解决这个问题？ (优于 n^2)

Answer 1

我能想到的最好的是O(n * k)时间和O(n + k)空间，其中 n是所有数组中元素的总数，k是数组的总数。在某种程度上我们可以并行执行一些检查(例如，如果数组引用的任意选择可以合理地表示为位集，例如 k <= 64 或小到足以组合其中的几个)，我们可以减少事实上的时间 O(n) .

简单地维护一个散列映射，其中每个看到的值都指向我们到目前为止遍历的数组的位集。对于每个遍历的数组，保留一个位集来表示它与哪些数组相交。对于当前遍历数组中的每个元素，OR该值的散列映射中的位集与数组的位集记录的交集。在横向结束时，非交叉点的数量增加了 k - pop_count(array_intersection_record) .