2011-11-21 80 views
0

如何检查列表中某些项目是否与theta(n)时间重复?检查列表中的重复项

它基本上意味着你不能检查每个项目的整个列表。

+0

计数排序? –

+0

你能否澄清一下你是否想要:a)只是摆脱重复的b)返回重复的c)只要知道*如果*有/是一个或多个重复? –

回答

1

迭代元素并将它们放入哈希映射(检查碰撞)。因为在散列映射中插入的是O(1),你最终应该用O(n)(迭代列表)+ O(1)(插入并检查散列映射的冲突,小鸡通常是一个操作大多数实现)以及O(n)+ O(1)→O(n)。