给定一个数组,并对索引`ij`进行一系列查询,如何有效地查找查询哪个索引的次数最多？

Question

给定一个数组A,从索引0到n-1哪里n是数组的大小,以及一系列形式的查询,i j其中,i与j指示指数(i和j包容性的),我该如何找出哪些指数已经查询数量最多的有效时间？

例如,考虑一个数组 [3,4,5,6,7,9]

和查询

0 3
3 5
1 2
2 4

Output
Index 0 has been queried 1 time.
Index 1 has been queried 2 times.
Index 2 has been queried 3 times.
Index 3 has been queried 3 times.
Index 4 has been queried 2 times.
Index 5 has been queried 1 time.

我该如何尽快做到这一点？

Answer 1

您可以在O(n + q)中执行此操作,其中n是数组的大小,q是查询的数量:

1. 使用n个条目创建空数组A.
2. 对于每个查询i,j将A [i]增加1并将A [j + 1]减1
3. 循环遍历数组计算累积总数并跟踪具有最高累积总数的索引

对于我们看到开始的每个区间,累计总数将包含+1,对于我们看到结束的每个区间,累计总数将包含-1.这意味着总数将给出当前打开间隔的计数,或者换句话说,查询条目的次数.