如何判断整型范围是否与整型列表重叠？
如何判断整型范围是否与整型列表重叠？
提问于 2013-03-23 01:59:22
例如:我们有一个列表：
1 2 3 7 8 9 11 12我们需要检查范围(A，B)是否与列表重叠，例如，范围(4，6)与列表不重叠，范围( 10，12)和范围(5，9)与列表重叠。我知道我们可以将列表放在一个hashSet中，然后我们只检查range中的任何元素是否出现在该集合中。这花费了O(N)。N是范围的长度。有没有更好的算法来解决这个问题？我知道有一种区间树数据结构，但我不太理解它。这种结构能在logN中解决这个问题吗？
回答 4
Stack Overflow用户
发布于 2013-03-23 02:09:55
看起来列表已经排序了；如果还没有，那就先排序。
假设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是列表中元素的数量。
Stack Overflow用户
发布于 2013-03-23 02:15:12
如果列表未排序：
O(M)，其中M是列表中的项数，是遍历列表，检查每一项，看是否低<=项<=高。
如果域是“合理”有界的，则可供选择：
将列表表示为位向量。将范围表示为位向量(此向量中的on位将是连续的)，然后将向量表示为“and”，以查看是否有位相同。
Stack Overflow用户
发布于 2013-03-23 02:11:12
如果对列表进行了排序，则可以找到将范围中的最小元素放置在列表中的位置，以及将范围中的最大元素放置在列表中的位置。这将花费2lg(N)时间。如果这些索引不同，则范围与列表相交。否则，我就不知道了。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15576972
复制相关文章
相似问题
腾讯云开发者
