python – 查找列表中最小的重复段

def shortest_repeating_sequence(inp):
    for i in range(1,len(inp)):
        if all(inp[j] == inp[j % i] for j in range(i,len(inp))):
            return inp[:i]

    # inp doesn't have a repeating pattern if we got this far
    return inp[:]

这段代码是O(n^2).最坏的情况是重复了很多次的一个元素,然后是在最后打破模式的东西,例如[1,1,8] .

从1开始,然后遍历整个列表,检查每个inp [i]是否等于inp [i％1].任何数字％1都等于0,因此您要检查输入中的每个项目是否等于输入中的第一个项目.如果所有项目都等于第一个元素,则重复模式是仅包含第一个元素的列表,因此我们返回inp [：1].

如果在某个时刻你遇到了一个不等于第一个元素的元素(all()一旦找到False就停止),你试试2.所以现在你要检查偶数索引处的每个元素是否是等于第一个元素(4％2为0),如果每个奇数索引等于第二个项目(5％2为1).如果你完成了这一步,那么模式就是前两个元素,所以返回inp [：2],否则再次尝试3,依此类推.

你可以做范围(1,len(inp)1)然后for循环将处理inp不包含重复模式的情况,但是你必须在最后不必要地迭代整个inp.并且你仍然必须在最后返回[]以处理inp作为空列表.

我返回列表的副本(inp [：])而不是列表以具有一致的行为.如果我返回带有返回inp的原始列表,并且某人在没有重复模式的列表上调用该函数(即他们的重复模式是原始列表),然后使用重复模式执行某些操作,则会修改其原始列表同样.

shortest_repeating_sequence([4,7,6])  # no pattern
[4,6]
shortest_repeating_sequence([2,3,3])  # pattern doesn't repeat fully
[2,1]
shortest_repeating_sequence([2,2])     # pattern doesn't repeat fully
[2,1]
shortest_repeating_sequence([8,8])
[8,9]
shortest_repeating_sequence([1,1])
[1]
shortest_repeating_sequence([])
[]