我有一些整数列表,如：
l1 = [8,9,8,8],l2 = [3,4,2,3]
我的目的是把它切成最小的重复片.所以：
output_l1 = [8,9]
output_l2 = [3,4]
每次序列未完全完成的最大问题.所以没有
‘abcabcabc’
只是
‘abcabcab’.
最佳答案
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([])
[]