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

Question

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

我知道nubOrd。它相当快。我们可以通过我们的列表，看看它是否变得更短。但效率nubOrd仍然不是线性的。

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

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

标签： algorithmhaskellcomplexity-theory

Answer 1

歧视包有一个你可以使用的线性时间节点。或者是一个线性时间组，它不需要等效元素相邻以便对它们进行分组，因此您可以查看是否有任何组的大小不是 1。

整个软件包基于通过使用基于“区分”而不是基于比较的算法来回避基于比较的排序（和连接等）的众所周知的界限。据我了解，该技术有点像基数排序，但推广到 ADT。