c - 使用辅助结构在 O(N) 时间内查找数组是否有重复项

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 5 年前。

Improve this question

我想知道在 C 中是否可以在 O(N) 时间内找到一个数组是否有重复项，但是您可以使用辅助数据结构，例如哈希表。请记住，数据结构中的插入也计算时间。感谢您的关注。

Answer 1

是的，哈希表可能有效。

对于每个单词，您计算哈希值并尝试将其插入表存储桶中。如果存储桶非空，则比较存储桶中的单词，如果新单词不存在，则将其添加到存储桶中，否则会发现重复的单词。

这意味着您仅处理输入的单词一次，但是，您可能需要多次检查存储桶中的单词。

处理输入的时间复杂度为 O(N)，处理存储桶是哈希表大小的函数。

大小为 1 的表将导致检查每个单词 N 次，因此时间复杂度为 O(N²)。表大小为 N 将导致每个单词检查 0 次，因此时间复杂度为 O(N)。