在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;
   

但是这也是不允许的.

所以有一个暗示我可以将数组本身用作hashset/hashtable和"线性散列"？

任何帮助？谢谢

Answer 1

维基百科定义的线性散列具有增量调整大小的优点，因为存储桶以循环方式一一分割，为调整大小的插入保留恒定的摊销时间复杂度。因此，他们的想法是迭代数组，重新使用已经迭代的元素作为线性散列的存储。

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

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

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

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