例如,如果我有一个列表
[1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]
此算法应返回 [1,2,3,4,5,6,7,8,9,10,11]。
为了澄清,最长的列表应该向前运行。我想知道执行此操作的算法有效方法是什么(最好不是 O(n^2))?
此外,我对不使用 python 的解决方案持开放态度,因为算法很重要。
谢谢。
最佳答案
这是一个简单的一次性 O(n) 解决方案:
s = [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11,42]
maxrun = -1
rl = {}
for x in s:
run = rl[x] = rl.get(x-1, 0) + 1
print x-run+1, 'to', x
if run > maxrun:
maxend, maxrun = x, run
print range(maxend-maxrun+1, maxend+1)
如果您考虑范围而不是端点和运行长度的单个变量,逻辑可能会更不言自明:
rl = {}
best_range = xrange(0)
for x in s:
run = rl[x] = rl.get(x-1, 0) + 1
r = xrange(x-run+1, x+1)
if len(r) > len(best_range):
best_range = r
print list(best_range)
关于python - 如何找到列表中不一定相邻的最大连续数字集?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8664708/