用于确定特定范围内有多少元素的数据结构？

Question

可以说我有一组数字.我需要计算给定范围内有多少个数字.例如:对于给定的集合{3, 4, 7, 10, 15, 30}::

numbers in range (0, 6) = 2
numbers in range (8, 40) = 3
numbers in range (0, 50) = 6

什么样的结构最适合这个目的？最好的意思是指具有最快执行所述操作的结构.此外,快速插入和删除也将受到赞赏......

Answer 1

如果给出的数字集永远不会改变,一个简单的选择是按照升序对数字进行排序,然后在范围的端点上使用二进制搜索来确定排序序列中第一个元素的位置.范围位于不在范围内的第一个元素所在的位置.然后,您可以减去这两个位置的差异,以计算范围内的元素数量,或者只是迭代该范围以确定该范围内的所有数字.使用快速排序算法(如快速排序或堆栈),可以在O(n log n)时间内完成排序,并且每个查询只需要时间O(log n)来执行两个不同的二进制搜索.

您可以通过各种方式加快速度.例如,如果您知道数字或多或少均匀分布,则可以使用插值搜索而不是二进制搜索来执行查找.这需要花费预期时间O(log log n)来执行每个查询,这比以前快得多.如果您知道这些数字都在[0,N]范围内,您可以使用更高级的数据结构,如van Emde Boas树,在最坏的情况下将所有操作加速到O(log log N).

另一方面,如果数字集可以增长和缩小,那么您可能需要考虑使用平衡二叉搜索树来存储数字.然后,您可以在树上进行有效搜索(在时间O(log n)中)以确定范围中的第一个数字和不在范围内的第一个数字.

希望这可以帮助!