algorithm - 最接近的相等数

Question

假设您有 a1..an数字和一些查询 [l, k] (1 < l, k < n) .问题是在[l, k]中找到interval 两个相等数之间的最小距离。

示例:(区间 l,k 显示为 |...|)

1 2 2 |1 0 1| 2 3 0 1 2 3

答案 2 (101)

1 |2 2| 1 0 1 2 3 0 1 2 3

答案 1 (22)

1 2 2 1 0 |1 2 3 0 3 2 3|

回答 2 (303) 或 (323)

我考虑过线段树，但是当查询在多个节点之间共享时，很难连接每个树节点的结果。我尝试了一些加入他们的方法，但它看起来很难看。有人可以给我提示吗？

---

澄清

感谢您的回答。问题是查询很多，所以o(n)不好。我没有不小心提到线段树。它执行 [l, r]查询查找 [l, r]SUM或 [l, r]MIN在数组中 log(n)复杂。我们可以在这里做一些预处理以适应 o(logn) 吗？

Answer 1

如果第一个数字等于最后一个数字但中间的每个数字在间隔中恰好出现一次，则称该间隔为最小。 11 和 101 是最小的，但 12021 和 10101 不是。

在线性时间(假设恒定时间散列)中，枚举所有最小间隔。这可以通过保留两个索引 l 和 k 以及一个将每个符号映射到 l 和 k 之间的 HashMap 来完成 到它的索引。最初，l = 1 和 k = 0。重复执行以下操作。增加 k(如果它太大，我们就停止)。如果 k 的新值处的符号在 map 中，则将 l 推进到 map 值，同时从 map 中删除内容。产生区间 [l, k] 并再次递增 l。在所有情况下，将 k 写为符号的映射值。

由于最小性，最小间隔按其左右端点以相同方式排序。为了回答查询，我们查找它可能包含的第一个区间和最后一个区间，然后发出区间范围长度的范围最小查询。理论上，结果是一种在线算法，该算法执行线性时间预处理并在恒定时间中回答查询，但为了方便起见，您可能不会以这种方式实现。