查找非重叠数组对的数量

本文介绍了查找非重叠数组对的数量的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

问题是要从给定的数组集中计算非重叠数组对的数量（对所有数组对进行计数，使它们没有任何公共元素）。

The problem is to count number of non-overlaping pairs of arrays (count all pairs of arrays such that they dont have any common elements) from given set of arrays.

例如，

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

The following pairs are non-overlaping (a,c), (a,d), (b,c), (b,d) since they dont have any element in common, so the answer to this instance of problem is 4

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

I have an n^2 solution which computes intersection of every array with every other array, and increments the count if the intersection is empty set.

有没有一种有效的方法来解决这个问题？ （优于n ^ 2）

Is there an efficient way to solve this? (better than n^2)

推荐答案

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

The best I can think of is O(n * k) time and O(n + k) space, where n is the total number of elements in all the arrays and k is the total number of arrays. To the extent we can perform some checks in parallel (for example, if an arbitrary selection of array references can be reasonably expressed as a bit set, e.g., k <= 64 or small enough to combine a few of them), we could reduce the time to defacto O(n).

只需维护一个哈希图，其中看到的每个值都指向一个比特集，到目前为止，我们遍历了该数组的所有位。对于每个遍历的数组，请保留一个位集，以表示与之相交的数组。对于当前遍历数组中的每个元素， OR 哈希映射中该值的位集与数组的交集的位集记录。在横切结束时，不相交的数量会增加 k-pop_count（array_intersection_record）。

Simply maintain a hash map where each value seen points to a bitset of which arrays we've traversed so far included it. For each traversed array, keep a bitset representing which arrays it intersects with. For each element in the current traversed array, OR the bitset in the hash map for that value with the array's bitset-record of intersections. At the end of the transversal, the number of not-intersections is augmented by k - pop_count(array_intersection_record).