java - 在 int 数组中查找第一个重复项，java

Question

这是我遇到的一个常见面试问题，但我未能按照要求的方式改进它。

assume we have an int array int[] A, we want to find the first duplicate entry. 

1. 几乎每个人都可以想到使用一个HashSet，并在解析时添加它。这将导致O(n)时间和O(n)空间。在此之后，我被要求在没有其他数据结构的情况下解决它。我说最愚蠢的想法是在 O(n^2) 时间内比较每一个。然后我被要求改进 O(n^2) 时间。

2. 为了改进它，我想到了使用一个固定大小的数组(假设最大数为n)，boolean[] b = new boolean[n];但是我不被允许使用这种方法。

3. 然后我想到了使用一个int变量，使用位操作，如果最大数小于32，那么对于n我们可以向左推1到n位，|到检查器，然后将检查器 & 到数组中的下一个条目以检查它是否 > 0。例如:

   int c = A[i];
   if(check & (1 << c) > 0) return false;
   check |= 1 << c;
   

但是这也是不允许的。

所以有一个提示，我可以将数组本身用作哈希集/哈希表和“线性哈希”？

有什么帮助吗？谢谢

Answer 1

线性哈希为 defined by Wikipedia具有调整大小增量发生的优点，因为桶以循环方式逐个拆分，保持不变的摊销时间复杂度以用于调整大小的插入。因此，他们的想法是迭代数组，重用已经迭代的元素作为线性哈希的存储。

虽然我远不是线性哈希方面的专家，但我看不出有任何方法可以将哈希表放入数组中。当然，要使用线性散列存储 n 个元素，您可能会使用 n 个存储桶。但是，桶中的元素数量是无限的，您需要像链表这样的东西来实现每个桶，这需要额外的 O(n) 内存用于指针。

因此，该算法不会产生比普通 HashSet 更好的渐近空间复杂度。不过，它确实将内存消耗减少了一个常数。

它的时间复杂度与普通的HashSet相当。

编辑:在我看来，这个答案被忽略了(没有投票，没有评论)。它没有用吗？请发表评论，以便我知道要改进的地方。