如何在一個巨大的數字列表中找到兩個數字，其中xi = xj？

Question

我有以下問題，並在我的尖叫聲與哈希的解決方案：

問題：

鑑於巨大的號碼列表，x1........xn其中xi <= T，我們想知道是否 或不存在兩個指數i,j，其中x_i == x_j。
在O(n)運行時間中找到算法，並且期望值爲O(n)。

我此刻解決方案：我們使用散列，我們將使用chaining有一個映射功能h(x)。

首先 - 我們建立一個新的數組，我們稱之爲A，其中每個單元格都是一個鏈表 - 這將是目標數組。

現在我們運行所有n數字，並使用散列函數將x1........xn中的每個元素映射到合適的位置。這將需要O(n)運行時間。

之後我們將在A上運行，並尋找衝突。如果我們找到一個單元，其中length(A[k]) > 1 然後我們返回xi和xj映射到存儲在A[k]中的值 - 對於最差的情況，總運行時間將是O(n)，如果兩個數字的映射值（如果它們確實存在）在A的最後一個單元格中。

Answer 1

同樣的方法可以快兩倍（平均），平均而言仍然是O(n) - 但具有更好的常數。

沒有必要所有的元素融入到哈希表，然後去在它 - 一個更快的解決方案可能是：

for each element e: 
    if e is in the table: 
     return e 
    else: 
    insert e into the table 

還要注意，如果T < n，必須有第一T+1元素中的欺騙，從pigeonhole principle。
也適用於小型T，您可以使用T大小的簡單數組，不需要散列(hash(x) = x)。 Initializing T can be done in O(1)包含零作爲初始值。