我有一个 0~9 的重复序列（但可以在这些数字中的任何一个开始和停止）。例如：
3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7, 8,9,0,1,2
它在随机位置有异常值，包括第一个和最后一个，例如：
9 ,4,5,6,7,8,9,0,1,2,3,4, 8 ,6,7, 0 ,9,0,1,2,3,4, 1 ,6,7, 8,9,0,1, 6
我需要查找并纠正异常值，在上面的示例中，我需要将第一个“9”纠正为“3”，将“8”纠正为“5”，等等。
我想出的是构建一个没有所需长度异常值的序列，但由于我不知道序列从哪个数字开始，我必须构建 10 个序列，每个序列从“0”、“1”开始， “2”...“9”。然后我可以将这 10 个序列与给定序列进行比较，并找到与给定序列最匹配的一个序列。然而，当重复模式变大时，这是非常低效的（比如如果重复模式是 0~99，我需要创建 100 个序列进行比较）。
假设不会有连续的异常值，有没有办法有效地查找和纠正这些异常值？
编辑：添加了一些解释并添加了算法标签。希望现在更合适。
我会对列表进行第一次扫描，以找到输入中保持正确顺序的最长子列表。然后我们将假设这些值都是正确的，并向后计算第一个值必须是什么才能在该子列表中生成这些值。
这是在 Python 中的样子：
def correct(numbers, mod=None):
if mod is None: # if argument is not provided:
# Make a guess what the range is of the values
mod = max(numbers) + 1
# Find the longest slice in the list that maintains order
start = 0
longeststart = 0
longest = 1
expected = -1
for last in range(len(numbers)):
if numbers[last] != expected:
start = last
elif last - start >= longest:
longest = last - start + 1
longeststart = start
expected = (numbers[last] + 1) % mod
# Get from that longest slice what the starting value should be
val = (numbers[longeststart] - longeststart) % mod
# Repopulate the list starting from that value
for i in range(len(numbers)):
numbers[i] = val
val = (val + 1) % mod
# demo use
numbers = [9,4,5,6,7,8,9,0,1,2,3,4,8,6,7,0,9,0,1,2,3,4,1,6,7,8,9,0,1,6]
correct(numbers, 10) # for 0..9 provide 10 as argument, ...etc
print(numbers)
这种方法的优点是，如果两个连续值出现错误，它甚至会给出一个很好的结果，当然前提是列表中有足够的正确值。
这仍然以线性时间运行。
我将提出@trincot 的好答案的变体。就像那个一样，它不关心一行中可能有多少异常值，但与那个不同的是，它也不关心一行中有多少不是异常值。
基本思想只是让每个序列元素“投票”决定第一个序列元素“应该是”什么。得票最多者获胜。通过构造，这最大化了保持不变的元素数量：在 1-liner 循环结束后，votes[i]如果i选择作为起点，则保持不变的元素数量。
def correct(numbers, mod=None):
# this part copied from @trincot's program
if mod is None: # if argument is not provided:
# Make a guess what the range is of the values
mod = max(numbers) + 1
votes = [0] * mod
for i, x in enumerate(numbers):
# which initial number would make x correct?
votes[(x - i) % mod] += 1
winning_count = max(votes)
winning_numbers = [i for i, v in enumerate(votes)
if v == winning_count]
if len(winning_numbers) > 1:
raise ValueError("ambiguous!", winning_numbers)
winning_number = winning_numbers[0]
for i in range(len(numbers)):
numbers[i] = (winning_number + i) % mod
return numbers
然后，例如，
>>> correct([9,4,5,6,7,8,9,0,1,2,3,4,8,6,7,0,9,0,1,2,3,4,1,6,7,8,9,0,1,6])
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
但
>>> correct([1, 5, 3, 7, 5, 9])
...
ValueError: ('ambiguous!', [1, 4])
也就是说，无法猜测您是否[1, 2, 3, 4, 5, 6]想要[4, 5, 6, 7, 8, 9]. 他们都有 3 个“正确”的数字，尽管在这两种情况下都没有两个相邻的异常值。
这是另一种使用groupby和count来自 Pythonitertools模块的方法：
from itertools import count, groupby
def correct(lst):
groupped = [list(v) for _, v in groupby(lst, lambda a, b=count(): a - next(b))]
# Check if all groups are singletons
if all(len(k) == 1 for k in groupped):
raise ValueError('All groups are singletons!')
for k, v in zip(groupped, groupped[1:]):
if len(k) < 2:
out = v[0] - 1
if out >= 0:
yield out
else:
yield from k
else:
yield from k
# check last element of the groupped list
if len(v) < 2:
yield k[-1] + 1
else:
yield from v
lst = "9,4,5,6,7,8,9,0,1,2,3,4,8,6,7,0,9,0,1,2,3,4,1,6,7,8,9,0,1,6"
lst = [int(k) for k in lst.split(',')]
out = list(correct(lst))
print(out)
输出：
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
编辑：
对于[1, 5, 3, 7, 5, 9]此解决方案的情况，将返回不准确的内容，因为我看不到您要修改哪个值。这就是为什么最好的解决方案是检查并提高 aValueError如果所有组都是单例。
像这样？
numbers = [9,4,5,6,7,8,9,0,1,2,3,4,8,6,7,0,9,0,1,2,3,4,1,6,7,8,9,0,1,6]
i = 0
for n in numbers[:-1]:
i += 1
if n > numbers[i] and n > 0:
numbers[i-1] = numbers[i]-1
elif n > numbers[i] and n == 0:
numbers[i - 1] = 9
n = numbers[-1]
if n > numbers[0] and n > 0:
numbers[-1] = numbers[0] - 1
elif n > numbers[0] and n == 0:
numbers[-1] = 9
print(numbers)