特定范围内某个数字出现的次数是多少？

Question

3

给定一个大的未排序的数组，我需要在特定范围内找出给定数字的出现次数。（可能有很多查询）

例如，如果arr[]={ 6,7,8,3,4,1,2,4,6,7,8,9}，left_range=3，right_range=7和number=4，则输出将为2。（考虑到一个从零开始索引的数组）

arr[i]可以在1到100000的范围内。数组中最多可以有100000个数字。

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

附注：允许对数组进行预处理。

- user3080029

如果您只需要进行一次查询，并且数组未排序，那么很可能最有效的方法是简单地取一个数组切片并进行暴力搜索。 - aruisdante

啊，如果在同一输入数组上可以有多个查询，请考虑将该数组转换为一个结构，使您可以在**O(log n)**时间内查询数字，并扩展该结构以让您缩小范围。换句话说，每个数字节点的记录将是包含该数字的索引。 - aruisdante

@aruisdante - 你是在建议使用类似线段树的数据结构吗？还是应该创建一个邻接表来存储所有数字，并仅存储它们出现的索引？ - user3080029

是的，这肯定可以转化为一个相对高效的树问题，虽然我不一定会使用分段技术。 - aruisdante

1

@NiklasB。你可能想使用map，这样你就可以存储带有数字的索引记录，但我试图不完全为他们解决作业问题。 - aruisdante

显示剩余13条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fallen · Accepted Answer

以下是不需要使用线段树的解决方案。

预处理:

回答问题：

对于任何查询，在vector[num]上执行二分查找，以找到num的最大索引的索引，该索引小于或等于右区间，我们称之为R。然后查找大于或等于左区间的最小索引，我们称之为L。打印 R - L + 1

运行时间：每个项目的预处理在O(1)内完成，总计O(N)时间。每个查询的答案：O(lg(N))

空间：假设使用vector或ArrayList，则空间相当线性。