Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
给你一组区间S。您必须以最小的时间复杂度找到S给定间隔中包含的所有间隔。(a, b)
S
(a, b)
这可以O(n)通过蛮力及时完成,其中n是 set 中的间隔数S。但是如果我被允许做一些预处理,这可以在更短的O(n)时间内完成吗?例如O(log n)时间?
O(n)
n
O(log n)
最初我在考虑区间树,但我认为它不适用于这里,因为区间树用于获取与给定区间重叠的所有区间。
您可以在 2D 平面中重塑您的问题。让(begin, end)每个区间的 是一个二维点。(请注意,所有有效间隔都将在对角线上结束)
(begin, end)
您的区间搜索问题使用具有或运行时的算法转换为经过充分研究的正交 2D 范围查询,其中 k 是报告的点数。
这里可以使用持久二叉搜索树。
预处理:
搜索:
搜索时间复杂度为 O(log(n) + m),其中 m 是输出中的元素数。