algorithm - 特定问题的数据结构？

Question

哪种数据结构可以在最坏情况下在 O(1) 时间内执行插入、删除和查找操作？

我们可以假设元素集是从有限集 1,2,...,n 中提取的整数，并且初始化可能需要 O(n) 时间。

我只能想到实现一个哈希表。

用树实现它不会为任何操作提供 O(1) 时间复杂度。或者有可能吗？？

请分享您对此或除此之外的任何其他数据结构的看法..

谢谢..

Answer 1

虽然这听起来像是家庭作业，但只要有足够的内存，您就可以只使用数组。访问任何一个元素都是 O(1)。如果您使用每个单元格来记录遇到了多少该类型的整数，插入也将是 O(1)。搜索将是 O(1)，因为它需要在该索引处索引数组并查看计数。这基本上就是基数排序的工作原理。