计算从另一点到另一点的可达性

Question

我有一个数组，它以排序的方式存储一组正x坐标，比如arr={1, 4, 5, 9, 12, 45}等等。

我有一个最大距离k，我可以从一个点到另一个点，让k=3。现在，考虑到两点x和y(arr[x]<arr[y])，我需要确定是否可以从x到y。如果两跳之间的距离小于或等于y，我将能够从x到达k。

在这里，假设x=1 y=4，那么我可以从1->2，然后2->3，但是由于3到4之间的距离大于3，我不能去，所以在这种情况下，我无法到达。

但是如果x=1和y=2那么我就能到达。

它可以简单地用O(n)来求解。我已经创建了一个从arr[x]到arr[y]的for循环，对于每一对点，我检查它们之间的距离是否小于或等于k。

但我需要更好的算法。我正在考虑做一些像二进制搜索这样的事情。有谁能提出一个好的算法吗？

Answer 1

如果你预先计算所有的答案，Lo0oks很容易做O(1)。

1. 生成一个最大差异的2D数组，以便maxdiffX，y = max(diffX，diffx+1...diff是)。自x
2. 请注意maxdiff(x，y) = max(maxdiff(x，z)，maxdiff(z，y))，因此较长序列的计算重用了在较短序列上所做的工作。先建最短的路，然后再建最短的路等等。
3. 如果maxdiffX，y <= k为真，则结果为真。

为了一个实际的实施，我会回忆录这个。也就是说，根据需要计算结果，并将结果保留到再次需要为止。一旦您为x构建了所有的maxdiffs .y，您就在两者之间建立了所有较短的距离，供以后使用。

这是一个典型的空间速度交换。

我相信这个算法对于单个值(x，y，k)是O(nlogn)，对于一个大的输入数据集，或者如果相同的(x，y，k)频繁发生，则该算法渐近地下降到O(n)。

如果数组很大，构建整个查找表可能是不切实际的，但是结合回忆录和部分构建的表仍然会为大型输入数据集提供返回。