在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

Wikipedia定义的线性散列的优势在于，调整大小可以递增地进行，因为存储桶以循环方式被一一拆分，从而为调整大小的插入保留了固定的摊销时间复杂度。因此，他们的想法是遍历数组，重新使用已经遍历的元素作为线性哈希的存储。

虽然我不是线性哈希专家，但我看不出任何方法可以将哈希表放入数组中。当然，要使用线性哈希存储n个元素，可以使用n个存储桶。但是，存储桶中的元素数量是不受限制的，因此您需要像链表那样的东西来实现每个存储桶，这会增加指针的O（n）内存。

这样，该算法不会比普通算法产生更好的渐近空间复杂度HashSet。但是，它确实将内存消耗减少了一个恒定的因素。

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

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