在多个链表中查找重复项的算法

Question

在多个(大型)链表中查找重复项的最快方法是什么。 我将尝试用数组来说明问题，而不是仅仅为了使其更具可读性。 (为了简单起见，我使用了 0-9 之间的数字而不是指针)。

list1[] = {1,2,3,4,5,6,7,8,9,0};
list2[] = {0,2,3,4,5,6,7,8,9,1};
list3[] = {4,5,6,7,8,9,0,1,2,3};
list4[] = {8,2,5};
list5[] = {1,1,2,2,3,3,4,4,5,5};

如果我现在问:“列表 1-5 中是否存在数字 8？”我可以对列表进行排序，删除重复项，对所有列表重复此操作并将它们合并到“ super 列表”中，然后查看(新)重复项的数量是否等于我搜索的列表数量。假设我得到了正确数量的重复项，我可以假设我搜索的 (8) 存在于所有列表中。 如果我改为搜索 1，我只会得到四个重复项 — 因此在所有列表中都找不到。

是否有更快/更智能/更好的方法来实现上述目标而无需以任何方式排序和/或更改列表？

P.S.:问这个问题主要是出于纯粹的好奇心，没有别的! :)

Answer 1

只需将每个数字放入哈希表中，并将该项目出现的次数存储在表中。当你找到另一个时，只需增加计数器。 O(n) 算法(所有列表中的 n 项)。

如果你想存储每个出现的列表，那么你还需要一个集合表示来存储在每个项目下。您可以使用任何集合表示形式——位向量、列表、数组等。这将告诉您该项目所属的列表。这并没有改变 O(n)，只是将工作量增加了一个常数。