如何确定一个点是否在一组区间内？

Question

我正在寻找最快的方法来确定一条线上的点是否在该线的子集内。我有一个整数点和一个“列表”，其中包含以下内容之一：

1. 由整数表示的点（3、10、1000等）
2. 由2个整数表示的区间（2:10是从2到10的所有整数，包括50:60等）

例如，如果我的点值为5，则返回true，因为它包含在一个区间内，对于55也是如此。如果我的点等于1000，则也返回true，因为它与点列表匹配。

我正在寻找一种快速的方法（比线性更快），以检查此条件，而无需实例化与可能的点数一样多的整数（即，对于1:1000区间，我不想实例化1000个整数）。这能在对数时间内完成吗？

谢谢

编辑： 您可以认为预处理数据列表所需的任何时间都等于0，因为一旦处理了我的初始区间，我需要将此测试应用于10,000个点。

- lezebulon

---

区间可以重叠吗？我不确定这是否有影响，但感觉应该有。 - Almo

他们可能可以，但我可以预处理我的数据，这样他们就不再需要了，时间上也没有问题，因为我使用相同的间隔集来处理10k个点。 - lezebulon

你需要知道一个点在哪些区间内，还是仅仅需要知道它是否在任何一个区间内？ - Karl Bielefeldt

澄清一下，这个“列表”可能看起来像这样？（3、2:10、10、50:60、1000）此外，对于一个有趣的问题加1。 - covertCoder

@Karl Bielefeldt：我只是返回了一个布尔值。 - lezebulon

Answer 1

嗯，也许您可以使用间隔或线段树：

• http://zh.wikipedia.org/wiki/线段树
• http://zh.wikipedia.org/wiki/区间树

- Samuel Gosselin

---

这是一个经过深入研究的计算几何问题（“一维刺穿查询”）。 - Nemo

Answer 2

如果您已经将整数范围排序，并且这些范围不重叠，则可以执行二进制搜索以在对数时间内找到正确的范围。

范围有任何限制吗？基于此，您可能可以想出散列函数以在常数时间内搜索。但这取决于您的约束条件。

- cgcoder

---

我认为可以假设范围在0到1000万之间。 - lezebulon

如果一些范围重叠，您可以对它们进行排序，并将重叠的范围合并为单个范围。 - Mark Ransom

Answer 3

经过思考，我认为下面的代码应该在对数时间内运行，不包括构建地图所需的时间:

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;
}

我认为只要地图被正确填充了不重叠的间隔，这个应该能够工作。

- lezebulon

Answer 4

首先检查一个点的哈希表。这是简单检查。

然后按第一个坐标对区间地图进行排序，然后找到该点的较低限制。

然后检查您是否包含在返回的元素中。如果您不在其中，则不在任何元素中。

- ex0du5

---

一些回复中似乎存在假设区间可能重叠的情况。解决此问题的数据结构由您控制，它不需要依赖于外部或初始区间集。因此，通常情况下不应存储重叠的区间 - 在插入到映射时将它们合并。在处理区间时，这是相当标准的做法。 - ex0du5

Answer 5

如果你有一个树形数据结构（我建议使用B树），你可以在次线性时间内完成，但不包括构建树所需的时间（大多数树需要n log n或类似的时间来构建）。

如果你只有一个简单的列表，那么最坏情况下你可能需要检查所有点和区间，因此你不能做得比线性更好。

- user1258361

Answer 6

你可以使用Bloom Filter来测试一个点，看看它不在一个区间内，在线性O(1)时间内。如果它通过了这个测试，你必须使用另一种方法，比如二分查找，以确定它是否确实是一个区间的一部分，在O(log n)时间内。

- Mark Ransom

---

@MatthiasVallentin，是的。布隆过滤器的大小取决于设置的点数和误报率概率，而不是可能输入范围的大小。 - Mark Ransom

谢谢，我现在明白你的想法了。然而，有很多选择可以最初固定Bloom过滤器参数。由于这种数据结构经常用于空间受限的环境中，一种常见的方法是假设一个固定的大小并设置基数来推导出k的最优值，即哈希函数的数量。您能否澄清一下您所说的“大小”是什么意思？一旦实例化，（基本）Bloom过滤器的大小通常不再改变。 - mavam

@MatthiasVallentin，抱歉我表达不清楚。我的意思是，一旦选择了点数、误报概率（以及哈希函数的数量），就可以计算出过滤器数组的大小。关键在于它不取决于输入范围。 - Mark Ransom