在 int 数组中查找第一个副本，java

algorithm java

2022-09-01 23:45:08

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

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

几乎每个人都可以想到使用HashSet，并在解析时添加它，这将导致O（n）时间和O（n）空间。在此之后，我被要求在没有其他数据结构的情况下解决它。我说最愚蠢的想法是在O（n^2）时间内比较每个。然后我被要求改善O（n^2）时间。
为了改进它，我想使用一个固定大小的数组（假设最大数字是n），布尔[] b = 新的布尔[n];但是我不允许使用此方法。
然后我想到使用int变量，使用位操作，如果最大数字小于32，那么对于n，我们可以将1位推到n位左转并|到一个检查器，然后和检查器到数组中的下一个条目，以检查它是否>0。例如：
```
int c = A[i];
if(check & (1 << c) > 0) return false;
check |= 1 << c;
```

但是，这也是不允许的。

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

任何帮助？谢谢

答案 1

维基百科定义的线性散列具有增量调整大小的优点，因为存储桶以轮循机制方式逐个拆分，保留了恒定的摊销时间复杂度，以便通过调整大小进行插入。因此，他们的想法是迭代数组，重用已经迭代的元素作为线性哈希的存储。

虽然我远非线性哈希专家，但我看不到任何方法可以将哈希表放入数组中。当然，要使用线性哈希存储 n 个元素，您可以使用 n 个存储桶。但是，由于存储桶中的元素数量是无限的，因此您需要一些类似链接列表的东西来实现每个存储桶，这需要为指针提供额外的O（n）内存。

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

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

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

答案 2

我有一个想法：当你沿着数组向下移动时，你对你访问过的部分进行排序。通过使用二进制搜索，您将节省时间;空间为 0。排序本身是...插入排序？你基本上像往常一样运行排序，但是当你搜索插入新数字的地方时，如果你点击数字本身，你就会大喊“宾果游戏”。这是对零空间+ O（n²）时间的改进。