在多個鏈接列表中查找重複的算法

在多個（大）鏈接列表中查找重複的最快方法是什麼？我會試着用數組說明這個問題，而不是爲了讓它更具可讀性。（爲了簡單起見，我使用了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

在多個鏈接列表中查找重複的算法

回答

相關問題