arrays - 如何在一个巨大的数字列表中定位两个数字，其中 xi=xj？

Question

我有以下问题，它向我尖叫着寻求哈希解决方案:

问题:

给定一个巨大的数字列表，x1........xn其中 xi <= T , 我们想知道是否存在两个索引i,j , 其中x_i == x_j .
在 O(n) 中查找算法运行时间，并且期望为 O(n) , 对于这个问题。

我目前的解决方案:我们使用哈希，我们将在其中使用映射函数 h(x)使用 chaining .

首先 - 我们构建一个新数组，我们称之为 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) 包含零作为初始值。