在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)