求基于约束条件构建配对组列表的高效方法

这里有个靠谱的高效实现思路，完全匹配你给出的示例要求，咱们拆解来看：

核心思路：排序+贪心分组 #

这个问题本质是要把元组聚成若干簇，簇里任意两个元组都得满足a差小于2、b差小于3。最关键的优化点是先按a值排序——因为排序后，只有相邻的元组才有可能满足a差<2（非相邻的a差肯定≥2，直接没法放一组），这样就能避免无意义的两两对比，大幅提升效率。

然后用贪心的方式逐步构建组：遍历排序后的元组，尽量把能加入当前组的元组都加进去，实在加不了就新开一个组。

具体步骤 #

1. 先给元组列表按a值排序 #

把所有元组按第一个元素（也就是a值）从小到大排好序。这一步是高效处理的基础，因为排序后我们只需要关注连续的元组，不用再考虑那些a差太大的元组。

2. 遍历排序后的列表，逐步建组 #

• 先初始化一个空的组列表，再把第一个元组作为第一个当前组的初始元素，同时记录当前组里b值的最小值和最大值（后面用来快速判断约束）。
• 从第二个元组开始逐个处理：
  • 先看a值约束：因为列表已经排序，当前元组的a值肯定≥当前组第一个元组的a值，所以只要判断这两个a的差是否小于2就行——如果差≥2，那这个元组和当前组所有元组的a差都≥2，直接新开组。
  • 如果a值符合要求，再看b值约束：这里不用挨个对比当前组的所有b值，只要看当前元组的b值是否落在[当前组最大b-2, 当前组最小b+2]这个区间里就行（整数情况下，这个区间等价于和组内所有b值的差都<3）。
  • 如果两个约束都满足，就把这个元组加入当前组，同时更新当前组的b值最小/最大值。
  • 只要有一个约束不满足，就把当前组存入结果列表，然后用这个元组新开一个组。
• 遍历结束后，别忘了把最后一个当前组也加入结果列表。

Python代码实现 #

def group_tuples(tuples_list):
    if not tuples_list:
        return []
    
    # 按元组第一个元素排序，这是高效处理的关键
    sorted_tuples = sorted(tuples_list, key=lambda x: x[0])
    
    groups = []
    # 初始化第一个组
    current_group = [sorted_tuples[0]]
    current_min_b = sorted_tuples[0][1]
    current_max_b = sorted_tuples[0][1]
    
    for t in sorted_tuples[1:]:
        a, b = t
        # 检查a约束：和当前组第一个元组的a差是否小于2（排序后组内所有a差都<2）
        first_a = current_group[0][0]
        if abs(a - first_a) >= 2:
            # 没法加入当前组，存下当前组并新开组
            groups.append(current_group)
            current_group = [t]
            current_min_b = b
            current_max_b = b
            continue
        
        # 检查b约束：用当前组的b极值快速判断
        if (b >= current_max_b - 2) and (b <= current_min_b + 2):
            # 可以加入当前组，更新组和b极值
            current_group.append(t)
            if b < current_min_b:
                current_min_b = b
            if b > current_max_b:
                current_max_b = b
        else:
            # 没法加入，存下当前组并新开组
            groups.append(current_group)
            current_group = [t]
            current_min_b = b
            current_max_b = b
    
    # 把最后一个组加入结果
    groups.append(current_group)
    return groups

# 测试你给的三个示例
print(group_tuples([(1, 2), (2, 3), (6, 4), (7, 5), (8, 15)]))
# 输出：[[(1, 2), (2, 3)], [(6, 4), (7, 5)], [(8, 15)]]

print(group_tuples([(1, 2), (2, 3), (6, 2), (9, 3), (10, 4)]))
# 输出：[[(1, 2), (2, 3)], [(6, 2)], [(9, 3), (10, 4)]]

print(group_tuples([(1, 2), (2, 3), (6, 2), (7, 4), (8, 15)]))
# 输出：[[(1, 2), (2, 3)], [(6, 2), (7, 4)], [(8, 15)]]

效率说明 #

• 排序阶段是整个算法的时间瓶颈，复杂度是O(n log n)，这已经是排序算法的最优复杂度了。
• 遍历分组阶段是O(n)，每个元组只处理一次，每次判断都是常数时间，非常高效。
• 空间复杂度是O(n)，用来存排序后的列表和分组结果，属于合理范围。

这个方法既保证了正确性，又把效率拉满，完全满足大规模数据的处理需求。

内容的提问来源于stack exchange，提问作者John M.