java - 对整数使用 HashSet

Question

我有两个列表。我想找到两者中最小的公共(public)数。我想到使用 HashSet 因为它不允许重复。我可以在向其中添加两个列表元素时找出常见数字。而 HashSet 的插入只需要恒定时间。这可以给我 O(n) 来找到两个中的最小共同点。但是HashSet如何在恒定时间内插入n个元素呢？在这种情况下，添加最后一个元素需要 O(n) 时间，因为要找到正确的存储桶，在最坏的情况下必须将哈希码与 n 个存储桶进行比较。请更正此问题并提前致谢..!

Answer 1

该算法看起来非常简单:

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

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