13

我想到了一个问题，如下：

我们有一个大小为 n 的整数数组 A，我们有测试用例 t，在每个测试用例中，我们都有一个数字 m 和一个范围 [s,e]，即给定 s 和 e，我们必须找到最接近的该数组范围内的 m 数（A[s]-A[e]）。

您可以假设数组索引是从 1 到 n。

例如：

  A = {5, 12, 9, 18, 19}
  m = 13
  s = 4 and e = 5

所以答案应该是18。

约束：

n<=10^5
t<=n

我能想到的只是每个测试用例的 O(n) 解决方案，我认为存在更好的解决方案。

4

3 回答 3

9

这是一个粗略的草图：从数据中创建一个段树。在每个节点上，除了左右索引等常规数据外，您还存储在以该节点为根的子树中找到的数字，按排序顺序存储。当您以自下而上的顺序构建分段树时，您可以实现这一点。在叶子正上方的节点中，您按排序顺序存储两个叶子值。在中间节点中，您将数字保留在左孩子和右孩子中，您可以使用标准合并将它们合并在一起。树中有 O(n) 个节点，保存这些数据应该花费总体 O(nlog(n))。

一旦你有了这棵树，对于每个查询，沿着路径走，直到你到达给定范围（[s，e]）中的适当节点。如教程所示，一个或多个不同的节点将组合形成给定的范围。由于树深度为 O(log(n))，即每次查询到达这些节点的时间。每个查询应该是 O(log(n))。对于完全位于范围内的所有节点，使用二进制搜索在存储在这些节点中的排序数组中找到最接近的数字。同样，O(log(n))。在所有这些中找到最接近的，这就是答案。因此，您可以在 O(log(n)) 时间内回答每个查询。

我链接到的教程包含其他数据结构，例如稀疏表，它们更容易实现，并且应该为每个查询提供 O(sqrt(n))。但我并没有考虑太多。

于 2013-01-07T16:33:21.143 回答
-1

我相当确定不存在更快的解决方案。您的问题的一个轻微变化是：

没有数组 A，但每个测试用例都包含要搜索的未排序数字数组。（从 s 到 e 的 A 的数组切片）。

在这种情况下，显然没有比对每个测试用例进行线性搜索更好的方法了。

现在，您的原始问题比上述变化更具体吗？唯一添加的信息是所有切片都来自同一个数组。我认为这个额外的约束不能用于算法加速。

编辑：我的立场得到纠正。段树数据结构应该可以工作。

于 2013-01-07T16:19:49.253 回答
-1

对数组进行排序并进行二进制搜索。复杂度：o(nlogn + logn *t)

于 2013-01-07T16:34:24.773 回答