算法-在小数组中检测重复数最好的算法是什么？

Question

在数组中检测重复数的最佳算法是什么，在速度、内存和避免开销方面是最好的。像5,9,13,3,2,5,6,7,1这样的小数组请注意，5 i重复。

在搜索和阅读了排序算法后，我意识到我将使用其中的一种算法，快速排序，插入排序或合并排序。

但实际上，我真的很困惑在我的例子中使用什么，它是一个小数组。

提前谢谢。

Answer 1

两种好的方法取决于您是否知道从中提取数字的范围。

情况1:范围是已知的。

假设您知道所有数字都在[a, b[范围内，因此该范围的长度为l=b-a。

您可以创建一个长度为l的数组，并用0s填充它，从而遍历原始数组，对于每个元素，e递增A[e-a]的值(在这里，我们实际上是在[0,l[中映射范围)。

完成后，您可以遍历A并查找重复的数字。事实上，如果存在A[i]大于1的i，则意味着i+a是一个重复的数字。

counting sort背后也有同样的想法，它也可以很好地解决您的问题。

情况2:范围未知。

很简单。稍微修改一下上面提到的方法，而不是使用数组，其中键是原始数组中的数字，值是您找到它们的时间。最后，遍历键集并搜索找到多次的键集。

备注。

在上面提到的两种情况下，复杂度都应该是O(N)，您不能做得更好，因为您至少必须访问所有存储值。看看第一个例子:我们迭代两个数组，它们的长度是N和l<=N，因此复杂度是最大的2*N，也就是O(N)。第二个示例确实有点复杂，并且依赖于映射的实现，但为了简单起见，我们可以安全地假设它是O(N)。

在内存中，您正在构造数据结构，其大小与原始数组中包含的不同值的数量成比例。

正如通常发生的那样，内存占用和性能是您选择的关键。前者越大，后者越好，反之亦然。正如在另一个响应中所建议的，如果您知道数组很小，那么您可以安全地依赖于复杂度为O(N^2)的算法，但这根本不需要内存。

哪一个是最好的选择？嗯，这取决于你的问题，我们不能说。