列表的属性:
必须为N,其中N是整数的数量
没有空单元格
数字可能不是完全连续的(即{-23,-15,-3,1,2,6,7,8,15,100})
插入/查找需要保持恒定的时间。
我的第一个本能是使用哈希表,但这将创建未使用的单元格,其中的数字将被跳过。
有什么办法可以构造这样的列表以在固定时间内检查该列表中是否存在数字?
根据我的评论,您可以使用Set
,根据您的确切用例,如果需要维护根据文档被认为是固定时间的顺序,则可以检出Java的HashSet或LinkedHashSet之类的东西:
像HashSet一样,它为基本操作(添加,包含和删除)提供恒定时间的性能,假设哈希函数将元素正确地分布在存储桶中。
如果您正在其他平台上寻找解决方案,也许有等效的实现,或者您可以检查Java的源代码并自己实现。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句