找到一種重複

兩種常用的方法來檢測在陣列中重複第三方式：找到一種重複

1）排序第一，時間複雜性爲O（n log n）的，空間複雜度O（1）

2）的散列設置，時間複雜度O（n），空間複雜度O（n）

是否有第三種方法來檢測重複？

請不要回答蠻力。

2011-05-10 Dante is not a Geek

相關：[有效的方法從數組中刪除重複的整數]（http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array） – 2011-05-12 03:56:36

另一個選項是Bloom filter。複雜性O(n)，空間不同（幾乎總是小於散列），但是存在誤報的可能性。數據集的大小，過濾器的大小以及您可以預期的誤報數量之間存在複雜的關係。

在進行更昂貴的重複檢查之前，布隆過濾器通常用作快速「完整性檢查」。

來源

2011-05-10 14:31:47 btilly

Hashset是解決這個問題的更嚴肅的解決方案。 – 2018-01-17 00:57:43

@KarimManaouil我也會先找到一個哈希集，但那是我們被要求不提供的潛在答案之一。布盧姆過濾器是大規模實踐中使用的第三種方法。 – btilly 2018-01-17 01:14:14

在數組非常大或處理設備是嵌入式系統的情況下，我同意bloom過濾器的使用，其中內存約束是特定實現的主要決定因素（尤其是，如果有義務實現O（N）時間複雜度）。無論如何，布隆過濾器比這種情況下有更好的使用情況（例如磁盤I/O，網絡）。 – 2018-01-17 14:22:01

取決於信息。

如果您知道數字的範圍，如1-1000，則可以使用位數組。

比方說的範圍是一個。B

使一個位陣列與（B-A）位。它們初始化爲0

遍歷數組，當你到了數x，在地方改變位X-A爲1

如果有一個1已經存在，你有一個重複。

時間複雜度：爲O（n）

空間複雜度：（B-A）位

來源

2011-05-10 09:31:39

的另一種方法，以找到重複設置n元件陣列包含從0到n-1個元素。 < Find Duplicates>

來源

2011-05-10 12:51:07 NirmalGeo

找到一種重複

回答

相關問題