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

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

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;
   

但这也是不允许的。

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

有什么帮助吗？谢谢

线性散列为由维基百科定义 http://en.wikipedia.org/wiki/Linear_hashing其优点是调整大小是增量进行的，因为存储桶以循环方式逐一分割，从而为调整大小的插入保留恒定的摊销时间复杂度。因此，他们的想法是迭代数组，重新使用已经迭代的元素作为线性散列的存储。

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

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

其时间复杂度与普通的相当HashSet.

编辑：在我看来，这个答案被忽略了（没有投票，没有评论）。是不是没啥用？请发表评论，以便我知道需要改进的地方。