查找副本的第三种方法

Question

检测数组中重复项的两种常见方法：

1)优先排序，时间复杂度为O (n log n)，空间复杂度为O (1)

2)哈希集，时间复杂度O (n)，空间复杂度O (n)

有没有第三种方法来检测重复的东西？

请不要回答暴力问题。

Answer 1

另一种选择是Bloom filter。复杂性O(n)，空间变化(几乎总是小于一个散列)，但存在误报的可能性。数据集的大小、过滤器的大小和您可以预期的误报数量之间存在复杂的关系。

Bloom过滤器通常被用作在进行更昂贵的重复检查之前的快速“健全检查”。

Answer 2

要看信息了。

如果你知道数字的范围，比如1-1000，你可以使用位数组。

假设范围是a...b

用(b-a)位组成一个位数组。将它们初始化为0。

循环数组，当你得到数字x时，将x-a位置的位改为1。

如果那里已经有一个1，那么你就有一个副本。

时间复杂度：O(n)

空间复杂度：(b-a)位

Answer 3

如果n个元素数组包含从0到n-1的元素，则另一种查找重复的方法。<Find Duplicates>