1

我有两个清单。我想找到两者中最小的公数。我想使用 HashSet 因为它不允许重复。我可以在向其中添加两个列表元素的同时找出常见的数字。HashSet 仅constant time用于插入。这可以让我O(n)找到两个中最小的共同点。但是 HashSet 怎么能插入n元素constant time呢？在这种情况下，添加最后一个元素需要O(n)时间，因为要找到正确的存储桶，在最坏的情况下必须将哈希码与 n 个存储桶进行比较。请更正这一点，并提前感谢..！

4

3 回答 3

1

该算法看起来很简单：

  1. 构造一个HashSet包含 list 元素的a A。
  2. 初始化min为像Integer.MAX_VALUE.
  3. 对于 中的每个元素B，测试它是否在HashSet. 如果是，并且小于min，则更新min。

无论如何，散列算法或多或少总是假设散列实际上是一个好的散列函数，并且您不必担心 O(n) 最坏的情况。

于 2012-07-11T13:37:18.397 回答
0

找到桶是恒定的时间——它只取决于给定对象的哈希值，而不是现有对象。

于 2012-07-11T13:36:23.673 回答
0

您可以在任何算法书籍（例如 Corman、Knuth）中找到答案。很快：bucketIndex = toPositiveInteger(hashcode()) % buckets.length

于 2012-07-11T13:36:46.977 回答