高效实现列表数值区间匹配并关联对应数据的方法

你的嵌套循环实现虽然直观，但确实会带来O(n*m)的时间复杂度——当list1和list2的元素数量增长时，这个复杂度会让运行速度急剧下降。咱们可以用排序+双指针的思路来优化，把时间复杂度降到O(n log n + m log m)，下面是具体的实现和解释：

核心思路 #

• 先对list1按lower_range（或者upper_range，因为你的list1里的区间是不重叠且连续的，按哪个排都一样）进行排序；
• 对list2按value进行排序；
• 用两个指针分别遍历排序后的list1和list2，匹配符合区间条件的元素，避免不必要的两两比对。

因为你的list1里的区间是不重叠且连续递增的（3-7，8-12，13-16），这个特性可以让双指针的逻辑更简洁：我们不需要回头遍历之前的区间，只要顺着往下找就行。

代码实现 #

list1 = [{'some_id': 1, 'lower_range': 3, 'upper_range': 7}, 
         {'some_id': 2, 'lower_range': 8, 'upper_range': 12}, 
         {'some_id': 3, 'lower_range': 13, 'upper_range': 16}]
list2 = [{'value': 4, 'data': 'A'}, 
         {'value': 8, 'data': 'B'}, 
         {'value': 9, 'data': 'C'}, 
         {'value': 15, 'data': 'D'}]

# 对两个列表排序
sorted_list1 = sorted(list1, key=lambda x: x['lower_range'])
sorted_list2 = sorted(list2, key=lambda x: x['value'])

list3 = []
ptr1 = 0  # 指向sorted_list1的当前区间
len1 = len(sorted_list1)

for item2 in sorted_list2:
    value = item2['value']
    # 找到第一个upper_range >= value的区间（因为区间递增，前面的区间肯定不符合）
    while ptr1 < len1 and sorted_list1[ptr1]['upper_range'] < value:
        ptr1 += 1
    # 检查当前区间是否包含value
    if ptr1 < len1 and sorted_list1[ptr1]['lower_range'] <= value <= sorted_list1[ptr1]['upper_range']:
        list3.append({'some_id': sorted_list1[ptr1]['some_id'], 'data': item2['data']})

# 输出结果与期望一致
print(list3)

为什么更高效？ #

• 排序的时间是O(n log n + m log m)，这比嵌套循环的O(n*m)要高效得多，尤其是当n和m都超过几百的时候，差距会非常明显；
• 双指针遍历是线性的O(n + m)，整个过程只需要遍历两个列表各一次，没有重复比对。

如果你的list1区间不是连续不重叠的，这个方法也可以调整适用——只需要在匹配时检查当前指针的区间，若不满足则移动指针，直到找到合适的区间或者遍历完所有区间。

额外优化点 #

如果list1的区间是固定且不会变化的，还可以把区间的上下限提取成单独的列表，用二分查找来快速定位每个value对应的区间，这样时间复杂度可以降到O(m log n)，对于list2特别大的场景会更友好：

import bisect

# 提取区间的upper_range和对应的some_id
upper_ranges = [item['upper_range'] for item in list1]
some_ids = [item['some_id'] for item in list1]

list3 = []
for item2 in list2:
    value = item2['value']
    # 用bisect找到第一个upper_range >= value的索引
    idx = bisect.bisect_left(upper_ranges, value)
    if idx < len(list1) and list1[idx]['lower_range'] <= value:
        list3.append({'some_id': some_ids[idx], 'data': item2['data']})

print(list3)

这个方法利用了二分查找的O(log n)特性，每个list2的元素只需要一次二分查找就能定位区间，非常适合list1小但list2极大的场景。

内容的提问来源于stack exchange，提问作者matnor