数据结构查找在一定范围内的整数数量在不变的时间

Question

说我有一个n整数数组 我需要创建一个数据结构，可以让我找到一些范围内的整数[a，b]在数组中。

我在想某种形式的计数排序？

Answer 1

任何有效的搜索算法都需要排序的输入数据。然后，您可以轻松地检索O（log（n））时间中的边界索引。

恒定时间检索可能只能通过生成查找表来实现。如果你知道a和b的界限，那应该不会太难。不过，你会为内存空间交易时间效率。猜猜这就是你的意思是“计数排序”。

Answer 2

快速排序数组。二进制搜索找到一个。从a遍历数组，直到找到b。

我猜你想这样做没有排序，否则问题太简单了。

如果数据未排序，则在读取数据之前无法知道最终值，因此每次都必须遍历整个数组。

Answer 3

是的，计数排序算法的计数部分适用于您。这基本上是什么 jackrabbit说。