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

在多个（大）链接列表中查找重复的最快方法是什么？我会试着用数组说明这个问题，而不是为了让它更具可读性。（为了简单起见，我使用了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 list1-5存在吗？'我可以对列表进行排序，删除重复项，对所有列表重复此操作并将它们合并到“超级列表”中，查看（新）重复项的数量是否等于我搜索的列表数。假设我得到了正确的重复数目，我可以假设我搜索的内容（8）存在于所有列表中。如果我改为搜索1，我只会得到4个副本— ergo未在所有列表中找到。

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

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

来源

2011-05-09 Waxhead

为什么你不只是遍历所有列表和搜索8的而不是排序/删除重复的故事吗？ – Klark 2011-05-09 22:13:36

@Klark我认为他知道任何一个查询的成本是O（n），使用那个平凡的算法，并且想要分摊多个查询的成本。 @Waxhead我认为你最好通过将它放置在树，散列表或计数布隆过滤器中来重新表示数据。 – 2011-05-10 19:05:23

定义的阵列hash并在list所有位置值设置为0

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

现在对于每个元素，在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)

现在你可以做hash_ptr[-6]或一些hash_ptr[i]与-SYMBOLS/2 < i < SUMBOLS/2 + 1

来源

2011-05-10 03:28:56 phoxis

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

如果您想存储每个出现的列表，那么您还需要在每个项目下存储集合表示。 YOu可以使用任何设置的表示法 - 位向量，列表，数组等。这将告诉您该项目是其成员的列表。这不会从O（n）改变它，只是增加一个常数的工作。

来源

2011-05-09 21:54:05

这个问题有点含糊，所以答案取决于你想要的。

哈希表是提出有关重复项的一般问题的正确答案，因为它允许您仅查看一次每个列表以构建可回答大多数问题的表;然而，有些问题并不需要一个。

可能的情况下，似乎回答你的问题：

你只需要知道，如果一定值存在于每一个列表？ - 检查第一个列表，直到找到值。如果没有，你就完成了：事实并非如此。重复每个连续列表。如果搜索到所有列表并找到该值，则将其复制到每个列表中。在这个算法中，没有必要查看每个列表中的每个值，甚至每个列表，因此这将是最快的。

您是否需要知道是否存在重复？ - 如果按数字键入的哈希表中的任何值的计数大于0，则会有重复项...如果您只需要知道这一点，则可以立即退出。

你需要在每张表中分别复制的数量吗？ - 将每个值乘以列表的数量并添加正在处理的列表的编号。将其存储为散列键并计数重复项。当处理完所有列表后，您将有一张表格可以回答各种问题。要检查特定值的重复项，请将其与列表计数相乘并检查顺序散列键。如果每个列表中都有一个，则该编号出现在每个列表中。如果在该范围内所有计数均大于1，则该数字将在每个列表中重复。

等等。

来源

2011-05-09 22:25:53 shipr

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

回答

相关问题