我正在寻找最快的方式来决定一条线上的点是否在此线的子集内。 我给定的整数点，我也有一个“清单”的任一：如何找到一个点是否在一组间隔内？
在这个例子中，如果我的点的值是5，那么我返回true，因为它包含在一个区间，相同的55.如果我的观点等于1000，我也返回true，因为它匹配点的列表。
我正在寻找一种快速方法（比线性更快）来检查这种情况，而不必像实际可能的点那样尽可能多的整数（即，对于1：1000的间隔我不想实例化1000个整数）。 这可以在对数时间内完成吗？
感谢
编辑： 可以考虑所采取的任何时间进行预处理的数据列表等于0，因为一旦我最初的间隔被处理，我需要这个测试适用于10,000点
首先检查点的hash_map。这是简单的检查。
然后，只需通过第一个坐标对间隔图进行排序，然后找到该点的lower_bound。
然后检查你是否包含在返回的元素中。如果你不是那样的话，那么你就不在其中。
似乎有一些假设在一些间隔可能重叠的答复中。您正在控制用于解决此问题的数据结构 - 它在外部或初始间隔集上没有必要的依赖关系。所以你不应该在一般情况下存储重叠间隔 - 在插入地图时加入它们。每当处理间隔时，这是相当标准的。 – ex0du5 2012-04-12 20:02:37
如果您有整数范围排序且范围不重叠，您可以执行二分查找以找到对数时间内的正确范围。
范围是否有任何限制？基于此，您可能会想出恒定时间搜索散列函数。但这取决于你的限制条件。
我想我可以假设范围在0到1000万之间。 – lezebulon 2012-04-12 19:59:11
如果某些范围重叠，您可以对它们进行排序并将重叠的范围折叠为一个范围。 – 2012-04-12 20:26:57
你可以在次线性时间内做到这一点GIVEN树数据结构（我推荐B树），如果你不计算建树的时间（大多数树需要n log n或类似的时间建立）。
如果你只是一个普通的列表，那么你不能做比线性更好，因为在最坏的情况下，你可能不得不检查所有点和间隔。
可以使用Bloom Filter测试点，看看它是否不在一个区间内，以线性O（1）时间。如果它通过该测试，则必须使用另一种方法（如二进制搜索）来查看它是否肯定是O（log n）时间间隔的一部分。
想要在间隔中散列每个点吗？ – mavam 2012-04-12 20:13:13
@MatthiasVallentin，是的。 Bloom Filter的大小取决于设置的点数和误报的可能性，而不是可能的输入范围。 – 2012-04-12 20:24:40
谢谢，我明白你的想法了。但是，布隆过滤器参数最初需要修改的选项很多。由于这种数据结构通常用于空间受限的环境，因此常用的方法是假定固定的大小和设置的基数来导出* k *的最佳值，即散列函数的数量。你能否澄清你的意思是“大小”？一旦实例化，（基本）布隆过滤器的大小通常不会再发生变化。 – mavam 2012-04-12 21:30:44
反思之后，我认为下面的代码应在对数时间的工作，但不包括构建地图所需的时间：
enum pointType {
point,
open,
close
};
std::map<long int, pointType> mapPoints;
mapPoints.insert(std::pair<long int, pointType>(3, point));
//create the 5:10 interval:
mapPoints.insert(std::pair<long int, pointType>(5, open));
mapPoints.insert(std::pair<long int, pointType>(10, close));
int number = 4;
bool inside = false;
std::map<long int, pointType>::iterator it1 = mapPoints.lower_bound(number);
if(it1->first == number || it1->second == close) {
inside = true;
}
我想这应该是地图上与非正确填写，只要工作 - 重叠间隔
可以重叠吗？我不确定这件事是否重要，但感觉应该如此。 – Almo 2012-04-12 19:52:57
他们可以，但我可以预处理我的数据，以便他们不再这样，这在时间上不是问题，因为我使用相同的时间间隔集合来处理10k点 – lezebulon 2012-04-12 19:54:48
他们是否订购？ – Freddy 2012-04-12 19:55:17