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

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};

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

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

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

Answer 1

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

如果要存储每个列表，则还需要在每个项目下存储一个集合表示形式。YOu 可以使用任何集合表示 - 位向量、列表、数组等。这将告诉您该项目所属的列表。这不会改变O（n），只是增加了一个常数因子。

Answer 2

定义一个数组hash并将所有位置值设置为 0

define hash[MAX_SYMBOLS] = {0};
define new_list[LENGTH]
defile list[LENGTH] and populate

现在，对于list中的每个元素，使用此数字作为hash的索引，并递增hash的位置。每次出现该数字都会使该hash位置的值增加一次。因此，重复的值i hash[i] > 1

for i=0 to (n - 1)
  do
    increment hash[list[i]]
endfor

如果要删除重复项并创建新列表，请扫描hash数组，并扫描每个存在i即hash[i] > 0按照它们在原始列表中出现的顺序将它们加载到新列表中。

define j = 0
for i=0 to (n - 1)
  do
    if hash[list[i]] is not 0
      then
        new_list[j] := i
        increment j
    endif
endfor

请注意，当使用负数时，您将无法直接使用这些值来索引。要使用负数，首先我们可以找到负数的最大量级，并在使用负数索引hash数组时使用该量级添加到所有数字中。

find the highest magnitude of negative value into min_neg
for i=0 to (n - 1)
  do
    increment hash[list[i + min_neg]]
endfor

或者在实现中，您可以分配连续内存，

然后在分配的内存块的中间定义一个指针，以便您可以前后移动，以便可以对其使用负索引。您需要确保有足够的内存在指针的前后使用。

int *hash = malloc (sizeof (int) * SYMBOLS)
int *hash_ptr = hash + (int)(SYMBOLS/2)

现在您可以使用-SYMBOLS/2 < i < SUMBOLS/2 + 1执行hash_ptr[-6]或一些hash_ptr[i]

Answer 3

这个问题有点模糊，所以答案取决于你想要什么。

哈希表是询问有关重复项的一般问题的正确答案，因为它允许您只浏览一次每个列表以构建一个可以回答大多数问题的表;但是，有些问题不需要一个。

似乎可以回答您问题的可能案例：

您是否只需要知道每个列表中是否存在某个值？ - 检查第一个列表，直到找到该值。 如果没有，你就完成了：它不是。 对每个连续列表重复此操作。 如果搜索所有列表并找到值，则在每个列表中都会重复该值。 在此算法中，无需查看每个列表中的每个值，甚至每个列表，因此这将是最快的。

您是否需要知道是否存在任何重复项？- 如果按数字键控的哈希表中的任何值的计数大于 0，则存在重复项... 如果这就是您需要知道的全部内容，您可以立即退出。

是否需要重复项的数量 在每个表中，分别？- 将每个值乘以列表数，然后添加正在处理的列表数。 将其存储为哈希键并计数重复项。 处理完所有列表后，您就有了一个可以回答各种问题的表。要检查特定值的重复项，请将其乘以列表计数并检查顺序哈希键。 如果每个列表都有一个，则每个列表中都存在该数字。 如果该范围内的所有计数都大于 1，则每个列表中都会重复该数字。

等。