java - 数组中的重复元素

Question

我有一个N个元素的数组，包含1到(N-1)个整数——从1开始到最大数N-1的整数序列——也就是说只有一个数是重复的，我要为了编写一个返回这个重复元素的算法，我找到了一个解决方案，但它只有在数组被排序时才有效，但事实可能并非如此。？

int i=0;
while(i<A[i])
{
i++
}
int rep = A[i];

Answer 1

我不知道为什么 RC 删除了他的评论，但他的想法很好。

有了 N 的知识，你可以很容易地计算出 [1:N-1] 的总和。然后总结你的数组中的所有元素并减去上面的总和，你就得到了你的数字。

这是以 O(n) 为代价的，并且是不可战胜的。

但是，这仅适用于您提到的先决条件。

一种更通用的方法是对数组进行排序，然后简单地遍历它。这将是 O(n log(n)) 并且仍然比您的 O(n²) 更好。

我知道你可以创建一个查找表并用全零初始化它的最大数量，遍历数组并检查一个并用一个标记条目。复杂度也只是 O(n)，但以内存为代价。

如果值范围未知，可以使用类似的方法，但可以使用哈希集代替查找表。