是否可以在 O(n) 中比较数组中的所有元素？

Question

我有一个长度为 n 的未排序数组。有没有办法在 O(n) 中找出数组中是否有相等的元素？

你知道你可以在 O(1)..

中读取数组

Answer 1

• 创建一个空字典
• 对于列表中的每个元素
  • 如果元素已经在字典中，return true
  • 否则将元素添加到字典
• 如果到达列表末尾，return false

Answer 2

考虑一个将每个元素映射到唯一整数的函数 foo，并且该整数集的范围是从 0 到 n。

然后您可以声明一个数组 arr 的布尔类型，大小为 n。

然后遍历元素数组，对每个元素调用 foo 以生成索引 i。您检查 arr[i] 以查看它是否已设置为 true。如果有，那么您就没有一组独特的元素。如果 arr 没有该元素，则设置 arr[i] = true.

这是 O(N)，但在存储方面很昂贵。