最近我被問到這個問題。鑑於連續不斷的單詞流，刪除重複內容
如果連續出現單詞流，請在讀取輸入時刪除重複項。
例子：
輸入：This is next stream of question see it is a question
輸出：This next stream of see it is a question
從年底開始，question以及is已經出現過一次，所以第二次它忽略。
我的解決辦法：
使用在這種情況下每個字過的流來散列。
如果發生碰撞，則忽略該單詞。
這絕對不是一個好的解決方案。我被要求優化它。
解決此問題的最佳方法是什麼？
散列並不是特別糟糕的解決方案。
它給出預期的O(wordLength)查找時間，但O(wordLength * wordCount)在最壞的情況下，並使用O(maxWordLength * wordCount)空間。
備選方案：
特里甲trie是樹形數據結構，其中每個邊緣對應於一個字母，從根的路徑限定的節點的值。
這會給O(wordLength)查找時間並使用O(wordCount * maxWordLength)空間，雖然實際空間使用可能（在下面的示例中例如te）是作爲重複前綴下只使用空間一次。
一個binary search tree是樹數據結構，其中在左子根的樹的每個節點比其父更小，同樣在右邊的所有節點都更大。
A self-balancing one給出O(wordLength * log wordCount)查找時間並使用O(wordCount * maxWordLength)空間。
甲bloom filter是由一些數位，並且其中字映射至位幾個散列函數的數據結構，設置每個哈希函數的輸出上的附加和檢查是否有任何未設置的查詢。
這比上述解決方案使用更少的空間，但是以誤報爲代價 - 有些詞語將被標記爲不重複。
具體而言，它使用1.44 log2(1/e)位每個密鑰，其中e是假陽性率，O(wordCount)空間使用率，但具有令人難以置信的低常數因子。
這會給O(wordLength)查找時間。
布隆過濾器的一個例子，表示所設置的
{x, y, z}。彩色箭頭顯示每個集合元素映射到的位陣列中的位置。元素w不在集合{x, y, z}中，因爲它散列到一個包含0的位數組位置。對於此數字，m=18和k=3。
'刪除'需要什麼？這兩次事件還是第二次？你是否將它們保存在某個地方？請舉例輸入/輸出。你目前的解決方案有什麼不好？ –
如果這個詞已經出現在流中一次。我們需要忽略它。這就是刪除的意思。不是兩個，在一次發生之後，其他人應該被忽略。 – Arvind