algorithm - 给定一个数组，以及对索引 `i j` 的一系列查询，我如何有效地找出哪个索引被查询的次数最多？

Question

给定一个数组 A，索引从 0 到 n-1 其中 n 是数组的大小数组，以及一系列形式为 i j 的查询，其中 i 和 j 表示索引(i 和 j inclusive), 如何找出哪个索引被有效查询次数最多？

例如，考虑一个数组[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。这意味着总数将给出当前打开间隔的计数，或者换句话说，该条目被查询的次数。