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

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 插入索引为 arr[i] 的二维向量(或 ArrayList)。

回答问题:

对于任何查询，对 vector[num] 进行二分搜索以找到该向量中小于或等于正确范围的 num 的最大索引的索引，我们称之为 R。然后找到大于的最小索引或等于左侧范围，我们称之为 L。打印 R - L + 1

运行时:每个项目的预处理时间为 O(1)，总时间为 O(N)。每个查询答案:O(lg(N))

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