algorithm - 如何在恒定时间内在 N 大小的列表中查找整数？

Question

列表的属性：

1. 大小必须为 N，其中 N 是整数的数量

2. 没有空单元格

3. 数字可能不是完全连续的（即 {-23,-15,-3,1,2,6,7,8,15,100}）

4. 插入/查找需要在恒定时间内。

我的第一个直觉是使用哈希表，但这会创建未使用的单元格，其中会跳过数字。

如果该列表中存在一个数字，是否可以构建这样的列表以检查恒定时间？

Answer 1

根据我的评论，您可以使用 a Set，具体取决于您的确切用例，如果您需要维护根据文档应该是恒定时间的顺序，您可以查看 Java 的HashSet或LinkedHashSet之类的东西：

与 HashSet 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在桶中正确地分散元素。

如果您正在寻找其他平台上的解决方案，也许有等效的实现，或者您可以查看 Java 的源代码并自己实现。