多列表间连续递增1元素模式查找及首元素返回需求

问题描述 #

给定若干数字列表，需从每个列表中各选取一个元素，组成连续递增1的序列（如第1个列表取x，第2个取x+1，第3个取x+2……以此类推），最终返回该序列的第一个元素x。

示例输入：

[545, 766, 1015]
[546, 1325, 2188, 5013]
[364, 374, 379, 384, 385, 386, 468, 496, 497, 547]

目标输出：545（对应序列545, 546, 547）

实现思路 #

1. 将所有输入列表转换为集合，利用集合O(1)时间复杂度的成员查询特性，提升查找效率；
2. 以第一个列表的元素作为候选起始值x，依次检查后续第i个列表是否包含x+i；
3. 找到第一个符合条件的x后立即返回，若遍历完所有元素都无匹配则返回None。

代码实现 #

def find_start_number(*lists):
    # 转换为集合加速查询
    set_list = [set(lst) for lst in lists]
    # 遍历第一个列表的所有候选起始值
    for start in lists[0]:
        valid = True
        for idx in range(1, len(set_list)):
            # 验证第idx个列表是否包含start + idx
            if (start + idx) not in set_list[idx]:
                valid = False
                break
        if valid:
            return start
    # 无匹配时返回None
    return None

# 测试示例1
list1 = [545, 766, 1015]
list2 = [546, 1325, 2188, 5013]
list3 = [364, 374, 379, 384, 385, 386, 468, 496, 497, 547]
print(find_start_number(list1, list2, list3))  # 输出: 545

# 测试示例2
list_a = [12, 64, 135, 23]
list_b = [84, 99, 65]
list_c = [66, 234, 7, 43, 68]
print(find_start_number(list_a, list_b, list_c))  # 输出: 64

扩展说明 #

• 如果需要收集所有符合条件的起始值，只需将return start改为将start添加到结果列表，遍历结束后返回列表即可；
• 若输入列表数量不固定，该代码也能自适应处理，无需修改逻辑。

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