例如：我们有一个列表：
1 2 3 7 8 9 11 12
我们需要检查范围 (A,B) 是否与列表重叠，例如范围 (4, 6) 与列表不重叠，范围 (10, 12) 和范围(5,9) 与列表重叠。我知道我们可以将列表放入 hashSet 中，然后我们只需检查范围内的任何元素是否出现在该集合中。这需要 O(N)。N 是范围的长度。有没有更好的算法来解决这个问题？我知道有一个区间树数据结构，但我不太明白。该结构可以在 logN 中解决这个问题吗？
问问题
766 次
5 回答
4
似乎列表已排序；如果还没有，请先对其进行排序。
让R = (start, end)我们要检查它是否重叠的范围。
我们可以对排序列表的位置start进行二分搜索：end
- 如果
start和end连续出现在列表中，那么它们不会重叠
例如
1 2 3 4 6 7 8 9 11 12
- 否则，列表中有一个元素位于它们之间，因此范围重叠
看：
1 2 3 7 8 9 10 11 12
这是O(log N)，其中N是列表中元素的数量。
于 2013-03-22T18:09:55.183 回答
3
如果列表未排序：
O(M) 其中 M 是列表中的项目 # 是遍历列表检查每个项目以查看是否低 <= 项目 <= 高。
如果域是“合理”有界的，则另一种选择：
将列表表示为位向量。将范围表示为位向量（此向量中的 on 位将是连续的）然后“和”向量以查看是否有共同的位。
于 2013-03-22T18:15:11.603 回答
1
如果列表已排序，您可以找到范围中的最小元素将被放置到列表中的位置，以及范围中最大的元素将被放置到列表中的位置。这将花费 2 lg(n) 时间。如果这些索引不同，则范围与列表相交。否则，我不知道。
于 2013-03-22T18:11:11.967 回答
1
显然，如果列表没有排序，那么任何为范围查询构建 ad hoc 结构的算法都将花费 O(n)。对列表进行排序将花费 O(n log n)。
使用集合（实现为平衡二叉树），将通过插入范围的下（或上）边界并检查下一个（或上一个）元素（数据结构）以 O(log 2 n) 输出结果必须支持该操作，这在二叉树上是微不足道的）。
一个非常有效的范围查询结构是B+tree，它可以让您在 O(log b n+k) 中找到一个范围，其中 b 是树的等级（即每个节点的子节点数）。请注意，这还将返回范围内的元素列表（例如，作为树数据集上的几个迭代器）。
另一个有趣的结构是Van Emde Boas树，它在 O(log log n) 中插入元素。使用与上述集合相同的技巧，我们可以找到具有相同时间复杂度的答案。另请参阅 X 快速尝试和 Y 快速尝试。
于 2013-03-22T19:00:21.020 回答
0
我知道您只想知道数组中是否存在 A 或 B。您无需使用排序，因为您只需执行 2 个步骤：
1- search that is there A or B in your array.(you can do it in O(n))
2- find minimum and maximum.(you can do it in o(n)).
您可以在 o(n) 内完全完成，并且您不能在小于 o(n) 的时间内完成，我在此链接中针对相同的问题对此进行了检查。
于 2013-03-23T01:01:10.010 回答