寻找点对应的区间

Question

我有 5 个元组 A, B, C, D 和 E 表示间隔。它们的交集是空的（对于它们中的每一对）并且它们是这样排序的，例如一个区间的上限小于下一个区间的下限。

例如：

A = (5, 10)
B = (21, 29)
C = (134, 160)
D = (900, 1050)
E = (1080, 1100)

intervals = [A, B, C, D, E]

我还有一个 X 点列表，按升序排列。

例如：

X = [6, 28, 130, 1000, 1129]

如您所见，X中的每一个数字可以属于也可以不属于一个区间。由于区间交集为空，每个数字最多属于一个区间。
此外，根据构造，每个间隔只有一个数字。

我想知道 X 中的每个数字属于哪个区间，如果有的话。
所以对于我的例子，输出应该是：

output = [(6, A), (28, B), (None, C), (1000, D), (None, E)]

表示数字6, 28, 1000分别属于区间A, B, D，没有数字属于区间C和E。

为了找出X中的每个数字属于哪个区间，我做了以下操作：

output = []
for interval in intervals:
    for number in X:
        if interval[0] <= number and number <= interval[1]:
            found_interval = True
            output.append((number, interval))
            break

    if not found_interval:
        output.append((None, interval))

这应该可行，但我认为应该有更快的方法。我想避免在每个间隔循环 X 。升级后的解决方案将遍历其余未找到任何间隔的数字。

有更快的方法吗？

Answer 1

[编辑时：我的原始代码没有正确处理 x 是正确端点之一的情况。修改后的代码修复了这个问题，扩展了测试示例以显示它如何处理其他边缘情况]

也许这会有所帮助：创建一个按排序顺序排列的所有端点的列表，如

ends = [5,10,21,29,134,160,900,1050,1080,1100]

并使用 bisect 模块查找点 x 在此列表中的位置。这是二分搜索，因此比线性搜索更有效。如果它落在两个索引 (i-1,i) 之间，其中 i 是奇数，则 x 在相应的区间内。否则它在 none.

此外，使用您的元组列表 intervals 加载排序的端点列表也很容易：

from bisect import bisect

def place(x,endpoints):
    i = bisect(endpoints,x)
    if i%2 == 0:
        if x == endpoints[i-1]:
            return endpoints[i-1],endpoints[i]
        else:
            return None
    else:
        return endpoints[i-1],endpoints[i]

A = (5, 10)
B = (21, 29)
C = (134, 160)
D = (900, 1050)
E = (1080, 1100)

intervals = [A, B, C, D, E]

ends = []
for interval in intervals:
    ends.extend(interval)

xs = [3, 5, 6, 10, 28, 130, 1000, 1129]

for x in xs:
    print(str(x),':',str(place(x,ends)))

输出：

3 : None
5 : (5, 10)
6 : (5, 10)
10 : (10, 21)
28 : (21, 29)
130 : None
1000 : (900, 1050)
1129 : None

Answer 2

您可以在线性时间内查找此问题的交叉点：

创建两个变量来跟踪当前值和区间索引。
只要您还没有遍历任一列表中的每个元素，请检查如果当前值属于区间。
如果该值属于当前区间，则将当前值和当前区间指数加一。由于值和区间都已排序且区间不重叠，没有其他元素可以属于当前区间，因此我们可以安全地向前移动。

如果该值小于当前区间的下限，增加当前值索引，因为该值也不能属于任何具有更大下限的区间。

如果该值大于当前区间的上限，增加当前区间索引，因为任何其他值也会大于该区间.

def find_intersection(values, intervals): output = [] value_index = 0 interval_index = 0 while value index < len(values) and interval_index < len(intervals): current_value = values[value_index] current_interval = intervals[interval_index] lower_bound, upper_bound = current_interval if current_value < lower_bound: output.append((None, current_value)) # This value cannot belong to any greater interval. value_index += 1 elif current_value > upper_bound: # No other value can belong to this interval either. interval_index += 1 else: output.append((current_interval, current_value)) # At most one value per interval and one interval per value. value_index += 1 interval_index += 1 # If we ran out of intervals all remaining values do not belong to any. for v in values[value_index:]: output.append((None, v)) return output

最坏的情况，没有数字属于任何区间，我们必须完全迭代每个列表（while 循环中的 intervals 和 for 循环中的 values），所以复杂度是 O(n + m)，其中 n 是值的数量，m 是间隔的数量。

寻找点对应的区间

Looking for corresponding intervals for points

python

search

loops

intervals