algorithm - 在 N 个列表中查找匹配项的有效方法？

Question

给定多个项目列表，找到具有匹配项目的列表。

这个问题的暴力伪代码如下:

foreach list L
    foreach item I in list L
        foreach list L2 such that L2 != L  
            for each item I2 in L2
                if I == I2
                    return new 3-tuple(L, L2, I) //not important for the algorithm

我可以想到许多不同的方法来解决这个问题 - 例如创建一个列表列表并在搜索其他候选列表后删除每个候选列表 - 但我想知道是否有更好的算法？

我正在使用 Java，如果这对您的实现有影响的话。

谢谢

Answer 1

1. 创建 Map<Item,List<List>>.
2. 遍历每个列表中的每个项目。
3. 每次触摸一个项目时，将当前列表添加到 map 中该项目的条目。

现在每个项目都有一个 Map 条目，告诉您该项目出现在哪些列表中。

这个算法大约是 O(N)，其中 N 是列表的数量(确切的复杂度将受 Map 实现的好坏影响)。我相信您的算法至少是 O(N^2)。

警告:我比较的是比较次数，而不是内存使用情况。如果您的列表非常庞大并且充满了大部分不重复的项目，那么我的方法创建的 map 可能会变得太大。