是否可以比較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）。 –

回答