python - 找到一个数字落入的一组范围

Question

我有一个 20 万行的数字范围列表，例如开始位置、停止位置。除了非重叠之外，该列表还包括所有类型的重叠。

列表看起来像这样

• [3,5]
• [10,30]
• [15,25]
• [5,15]
• [25,35]
• ...

我需要找到给定数字所在的范围。并将对 100k 个数字重复此操作。例如，如果 18 是上面列表中的给定数字，则函数应返回[10,30][15,25]

我正在使用对分法以过于复杂的方式进行操作，任何人都可以提供有关如何以更快的方式进行操作的线索。

谢谢

Answer 1

这似乎是一个范围覆盖问题。由于您有大量查询要处理，因此您需要尽快给出结果。这个问题有一个算法，你可以看看Segment Tree .

想法是先根据给定的区间建立一个Segment Tree，然后对于每一个query，你可以做到log(N)一样快, 其中N是区间数。

获取所有可能的k区间，首先找到覆盖所有子区间的父节点log(n) ，然后遍历它的子节点以检索所有 k 个区间。因此，检索给定数字的所有区间的时间复杂度受 log(N) + O(k) 限制。 , 其中k << n .

这个算法可能会变慢到 O(N)当所有间隔都包含给定的数字时。在这种情况下，由于输出的大小是 N , 不存在更好的解决方案。因为算法的复杂度必须至少与输出大小同阶或更高。

希望对您有所帮助。