1

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

问题 ：

给定一个巨大的数字列表x1........xnwhere xi <= T，我们想知道是否存在两个索引i,jwhere 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。

4

1 回答 1

3

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

无需将所有元素映射到哈希中然后遍历它 - 更快的解决方案可能是：

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

另请注意，根据鸽巢原理，如果 ，则第一个元素T < n内必须存在欺骗。 同样对于小型，您可以使用大小为 T 的简单数组，不需要散列。初始化 T 可以包含零作为初始值。T+1
T(hash(x) = x)O(1)

于 2012-06-20T09:32:38.950 回答