python - 如何找到列表中不一定相邻的最大连续数字集？

Question

例如，如果我有一个列表

[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 的解决方案持开放态度，因为算法很重要。

谢谢。

Answer 1

这是一个简单的一次性 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)