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

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？' 我可以对列表进行排序,删除重复项,对所有列表重复此操作并将它们合并到"超级列表"中,并查看(新)重复项的数量是否等于我搜索的列表数量.假设我得到了正确的重复数,我可以假设我搜索的内容(8)存在于所有列表中.如果我改为搜索1,我将只得到四个重复项 - 并未在所有列表中找到.

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

PS:这个问题主要是出于纯粹的好奇心而没有别的!:)

Answer 1

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

如果要存储每个列表中的列表,则还需要在每个项目下存储一组表示.你可以使用任何集合表示 - 位向量,列表,数组等.这将告诉你该项目所属的列表.这不会从O(n)改变它,只是通过常数因子增加工作量.