3

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

示例：（间隔 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]查询。我们可以在这里做一些预处理以适应 o(logn) 吗？[l, r]SUM[l, r]MINlog(n)

4

2 回答 2

1

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

在线性时间（假设恒定时间散列），枚举所有最小间隔。这可以通过保留两个索引l和，以及将每个符号映射到其索引之间的k哈希映射来完成。最初，和。重复执行以下操作。增量（如果它太大，我们停止）。如果新值的符号在地图中，则前进到地图值，边走边从地图中删除东西。产生间隔并再次增加。在所有情况下，写为符号的映射值。lkl = 1k = 0kkl[l, k]lk

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

于 2015-03-14T13:55:01.677 回答
1

我们可以O(nlog(n))通过排序来做到这一点。首先，用它们的原始索引标记 [l,k] 中的所有元素。然后，对 [l,k] 中的元素进行排序，首先根据值，其次根据原始索引，均升序。

然后，您可以遍历排序列表，保留一个currentValue变量，并检查距离相同的相邻值，并minDistance在必要时进行设置。currentValue当您在排序列表中达到新值时更新。

假设我们[l,k]从您的第二个示例中有这个范围：

1 2 3 0 3 2 3

我们可以将它们标记为

1(1) 2(2) 3(3) 0(4) 3(5) 2(6) 3(7)

并将它们排序为

0(4) 1(1) 2(2) 2(6) 3(3) 3(5) 3(7)

循环这个，0和1没有范围。2s的最小距离是4，3s的最小距离是2（[3,5]或[3,7]，取决于你是否minDistance在新的最小距离等于当前最小距离）。

因此我们得到

[3,5] in [l,k] or [5,7] in [l,k]

编辑

由于您提到了一些查询，您可以O(nlog(n))及时对列表进行预处理，然后仅对O(n)每个单独的查询使用时间。在遍历排序列表时，您只需忽略不在 [l,k] 中的索引。

编辑 2

这是解决问题中的澄清问题，该问题现在指出总会有很多查询要运行。我们可以O(n^2)使用动态编程及时预处理，然后O(1)及时运行每个查询。

首先，对我上面描述的整个列表执行预处理。然后从原始列表中及时形成链接O(n)到排序列表中。

我们可以想象：

[l,k] = min([l+1,k], [l,k-1], /*some other sequence starting at l or ending at k*/)

我们有一个基本案例

[l,k] = infinity where l = k

如果[l,k]不是min([l+1,k], [l,k-1])，那么它要么开始于l要么结束于k。我们可以采取其中的每一个，查看排序列表并以正确的方向查看相邻元素并检查距离（确保我们在界限内）。我们只需要检查 2 个元素，因此它是一个常数因子。

使用这个算法，我们可以运行以下

for l = n downto 1
    for k = l to n
        M[l,k] = min(M[l+1,k], M[l,k-1], sequence starting at l, sequence ending at k)

您还可以将解决方案存储在矩阵中（实际上是一个金字塔）。然后，当你得到一个查询时[l,k]，你只需在矩阵中查找它。

于 2015-03-14T14:07:09.320 回答