如何测试整数范围与整数列表是否有重叠？

Question

例如： 我们有一个列表：

1 2 3 7 8 9 11 12

我们需要检查一个区间(A,B)是否与列表重叠，例如，区间(4,6)与该列表不重叠，而区间(10,12)和区间(5,9)与该列表重叠。我知道我们可以将列表放入HashSet中，然后只需检查范围内的任何元素是否出现在该集合中。这个方法的时间复杂度是O(N)，其中N是范围的长度。是否有更好的算法来解决这个问题？我知道有一种称为区间树的数据结构，但我不太理解它。那个数据结构能否以logN的时间复杂度解决这个问题？

- Yijie Li

---

请问您能解释一下重叠的确切含义吗？(A,B)是开区间吗（即不包含A和B）？为什么(5,9)会重叠？ - Knoothe

Answer 1

似乎列表已经排序；如果没有，则先对其进行排序。

假设我们要检测是否有重叠的范围，记为R = (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 是列表中元素的数量。

- abeln

---

这是假设范围是开放的，并且我们可以随机访问列表中的元素，对吗？ - didierc

如果范围是闭合的，那么这个想法是类似的。“数组”比“列表”更加恰当。 - abeln

Answer 2

如果列表没有排序：

遍历列表，检查每个项以查看是否满足 low <= item <= high 。这将花费 O(M) 的时间，其中 M 是列表中的项目数量。

---

如果域是“相当”有限的：

将列表表示为位向量。将范围表示为位向量（此向量中的打开位将是连续的），然后对向量执行“and”操作以查看是否存在共同的位。

- Dale Wilson

Answer 3

如果列表已排序，则可以找到范围中最小元素在列表中的位置和最大元素在列表中的位置。这需要2 lg(n)时间。如果这些索引不同，则范围与列表相交。否则，我不知道。

- user2200390

Answer 4

显然，如果列表没有排序，则任何构建用于范围查询的临时结构的算法都将需要O(n)时间。对列表进行排序将需要O(n log n)时间。

使用集合（实现为平衡二叉树）将在O(log2n)时间内产生结果，通过插入范围的下限（或上限），并检查下一个（或上一个）元素来实现（数据结构必须支持此操作，在二叉树上很简单）。

一种非常有效的范围查询结构是B+tree，它可以在O(logb n+k)的时间内找到范围，其中b是树的等级（即每个节点的子节点数）。请注意，这也将返回范围内的元素列表（例如作为树数据集上迭代器的一对）。

另一个有趣的结构是Van Emde Boas树，它以O(log log n)的时间插入元素。使用与上述集合相同的技巧，我们可以在相同的时间复杂度下找到答案。还可以参考X快速trie和Y快速trie。

- didierc

Answer 5

我理解您只想知道您的数组中是否存在A或B。您无需使用排序，因为您只需要执行两个步骤：

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)的时间内完成它，我在这个link中对同样的问题进行了检查。

- amin k