返回列表中各连续递增分组首元素的所有索引

需求说明 #

查找列表中所有连续递增（相邻元素差值为1）数值序列的起始索引。

• 测试输入：lst = [0,1,2,7,8,9]
• 预期输出：[0,3]

实现方案（Python） #

def get_sequence_start_indexes(input_list: list[int]) -> list[int]:
    # 空列表直接返回空结果
    if not input_list:
        return []
    start_indexes = [0]
    # 从第二个元素开始遍历判断
    for idx in range(1, len(input_list)):
        # 不满足连续递增规则时，当前索引就是新序列起点
        if input_list[idx] != input_list[idx-1] + 1:
            start_indexes.append(idx)
    return start_indexes

# 验证示例
if __name__ == "__main__":
    test_lst = [0,1,2,7,8,9]
    print(get_sequence_start_indexes(test_lst))  # 输出: [0, 3]

逻辑解释 #

• 列表首元素必然是第一个连续序列的起点，直接初始化到结果列表中
• 遍历过程中只要发现当前元素和前一个元素的差值不是1，就说明连续序列在此处断裂，当前位置是下一段连续序列的起点
• 算法时间复杂度为O(n)，仅需一次遍历即可得到结果，空间复杂度为O(k)，k为列表中连续递增序列的段数

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