给定一个大型未排序数组,我需要找出给定数字在特定范围内出现的次数。 (可以有很多查询)
例如如果 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:允许对数组进行预处理。
最佳答案
这是一个不需要线段树的解决方案。
预处理:
- 对于每个数字
arr[i]
,将 i 插入索引为arr[i]
的二维向量(或 ArrayList)。
回答问题:
对于任何查询,对 vector[num] 进行二分搜索以找到该向量中小于或等于正确范围的 num 的最大索引的索引,我们称之为 R。然后找到大于的最小索引或等于左侧范围,我们称之为 L。打印 R - L + 1
运行时: 每个项目的预处理时间为 O(1),总时间为 O(N)。 每个查询答案:O(lg(N))
空间:相当线性的假设向量或ArrayList
关于arrays - 特定范围内数字的出现次数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22433032/