arrays - 查找一组数组中常见的元素集

Question

假设有几个数组:

A. [1,2,3,4,5,6,7,8,9,10]
B. [2,4,6,8,10]
C. [1,4,7,10]
D. [1,3,5,7,9]
.
.

我需要找出所有可能的元素集 (1,2,3,4,5 ...)，每个元素在至少 2 个数组 (A,B,C...) 中是常见的，并且按以下方式显示它们:

(2,4,6,8,10) -> (A,B)
(1,4,7,10) -> (A,C)
(1,3,5,7,9) -> (A,D)
(4,10) -> (A,B,C)
(1,7) -> (A,C,D)

实际输入是包含字符串的文件。可能有数千个文件，每个文件可能包含一百多个关键字符串。

我尝试了以下方法:首先，我通过比较所有可能的数组对来生成元素集。然后我尝试使用逻辑生成其他集合 - 元素集的交集在数组集的并集中很常见。像这样:

(2,4,6,8,10) -> (A,B)
(1,4,7,10) -> (A,C)

从上面我们可以得到:

    intersect((2,4,6,8,10),(1,4,7,10)) -> union((A,B),(A,C))
or, (4,10) -> (A,B,C)

是否有任何其他方法可以尝试改善时间和内存复杂性 - 考虑每个包含数百个元素的数千个输入文件？

Answer 1

我会使用以下方法。

1. 扫描整个数据以获得数据中出现的一组元素。
2. 为每个元素维护一个计数器；再次扫描数据并在每个元素出现时增加计数器。
3. 丢弃所有出现次数少于 2 次的元素。
4. 生成剩余元素的所有可能子集。对于每个子集，扫描数据并在集合中的任何元素出现时输出每个数组标识符。