在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条目,告诉您该项目出现在哪个列表中.

该算法约为O(N),其中N是列表的数量(确切的复杂性将受到Map实现的好坏的影响).我相信你的算法至少是O(N ^ 2).

警告:我正在比较比较次数,而不是内存使用情况.如果您的列表非常庞大并且大部分都是非重复项目,那么我的方法创建的地图可能会变得太大.