是否可以比较O（n）中数组中的所有元素？

我有一个长度为n的未排序数组。有没有办法找出O（n）中数组中是否有相同的元素？是否可以比较O（n）中数组中的所有元素？

你知道你可以从阵列中O读（1）..

2016-11-30 M. Dou

阵列中有什么？如果是整数，那么可能的范围是什么？ – Bathsheba

是否允许额外的空间？好的。否则没有 – thebenman

考虑一个功能foo每个元素映射到一个唯一的整数，而整数集从0一定到n。

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

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

这是O（N），但在存储方面很昂贵。

2016-11-30 13:55:03 Bathsheba

我不认为在O（n）中创建数组是可能的，是吗？ –

这是对OS的调用，肯定不会比O（n）更差。 *初始化*它是O（n）。 – Bathsheba

2016-11-30 13:50:56

我认为这是因为插入到字典中不是O（1）。你只是在复杂的道路上踢球。 – Bathsheba

为什么不呢？ https://wiki.python.org/moin/TimeComplexity#dict –

Tbh我从来没有听说过字典的数据结构。但通过字典运行并检查所有与我正在比较的元素相同的元素不能在log（n）下完成，可以吗？所以我仍然需要n * log（n）。 –

回答