algorithm - 我可以在线性时间内检查有界列表是否包含重复项吗？

Question

假设我有一个 Int 列表，其中的元素已知是有界的，并且已知该列表不超过它们的范围，因此它完全有可能不包含重复项。我怎样才能最快地测试是否是这种情况？

我知道nubOrd .是quite fast .我们可以传递我们的列表，看看它是否变短了。但是 nubOrd 的效率仍然不是线性的。

我的想法是我们可以用空间换取时间效率。势在必行，我们将分配一个与我们的范围一样宽的位域，然后遍历列表，标记与列表元素值对应的条目。一旦我们尝试翻转已经为 1 的位，我们就会返回 False。它只需要 (read + compare + write) * 列表的长度。没有二叉搜索树，什么都没有。

在 Haskell 中尝试类似的构造是否合理？

Answer 1

discrimination包有线性时间nub您可以使用。或者线性时间 group不需要相邻的等效元素即可对它们进行分组，因此您可以查看是否有任何组的大小不是 1。

整个包的基础是通过使用基于“歧视”而不是基于比较的算法来回避众所周知的基于比较的排序(和连接等)的界限。据我了解，该技术有点像 radix sort , 但推广到 ADT。