检测数组中重复元素的两种常见方法：
1）先排序，时间复杂度O(n log n)，空间复杂度O(1)
2）哈希集合，时间复杂度O(n)，空间复杂度O(n)
是否有第三种检测重复的方式？
请不要使用暴力解法。
3个回答
5
另一个选择是布隆过滤器。时间复杂度为
在进行更昂贵的重复检查之前，常常使用Bloom过滤器进行快速的“合理性检查”。
O(n)，空间占用不定（几乎总是小于哈希表），但有可能出现误判。数据集大小、过滤器大小以及预期的误判次数之间存在复杂的关系。在进行更昂贵的重复检查之前，常常使用Bloom过滤器进行快速的“合理性检查”。
- btilly
4
一个Hashset是这个问题的一个更严肃的解决方案。 - Karim Manaouil
@KarimManaouil 我也会首先选择哈希集，但这是我们被要求不提供的潜在答案之一。布隆过滤器是第三种实际应用于大规模数据的方法。 - btilly
如果数组非常大或处理设备是嵌入式系统，内存限制是特定实现的主要决策因素（尤其是如果必须实现O（N）时间复杂度），我同意在这种情况下使用布隆过滤器。无论如何，布隆过滤器比这种情况有更好的使用案例（例如磁盘I/O、网络）。 - Karim Manaouil
@KarimManaouil 我同意。这是一种权衡，通常布隆过滤器并不是正确的答案，但当你需要它们时，知道这个选项是很好的。 - btilly
4
根据所需信息而定。
如果您知道数字范围，比如1-1000，可以使用位数组。
假设范围是a...b
创建一个有(b-a)个位的位数组。将它们初始化为0。
遍历数组，当到达数字x时，将x-a位置上的位更改为1。
如果那里已经有一个1，那么就有重复数字。
时间复杂度：O(n)
空间复杂度：(b-a) 位
如果您知道数字范围，比如1-1000，可以使用位数组。
假设范围是a...b
创建一个有(b-a)个位的位数组。将它们初始化为0。
遍历数组，当到达数字x时，将x-a位置上的位更改为1。
如果那里已经有一个1，那么就有重复数字。
时间复杂度：O(n)
空间复杂度：(b-a) 位
- Yochai Timmer
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接