python - 寻找点对应的区间

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

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

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

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

  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 是间隔的数量。