特定范围内的数字出现次数？

Question

给定一个大的未排序数组,我需要找出特定范围内给定数字的出现次数.(可以有很多查询)

例如,如果ARR []={ 6,7,8,3,4,1,2,4,6,7,8,9}和left_range=3和right_range=7和number=4,然后输出将是2.(考虑0索引阵列)

arr [i]可以在1到100000的范围内.阵列最多可以有100000个数字.

你能指导我在这里使用哪种数据结构或算法吗？

PS:允许预处理数组.

Answer 1

这是一个不需要分段树的解决方案.

预处理:

1. 对于每个数字arr[i],将i推送到带有索引的2D矢量(或ArrayList)arr[i].

回答查询:

对于任何查询,在vector [num]上进行二元搜索,找到该向量中num的最大索引的索引,该索引小于或等于right range,让我们称之为R.然后找到大于或等于的最小索引左边的范围,我们称之为L.打印R - L + 1

运行时:每项O(1)预处理,总O(N)时间.每个查询答案:O(lg(N))

空间:相当线性假设向量或ArrayList