在python中，如何有效地找到列表中不一定相邻的最大连续数字集？

  • Z时代
  • 2024-01-10
  • 分类：问答

例如，如果我有一个列表

[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中，如何有效地找到列表中不一定相邻的最大连续数字集？ 的全部内容， 来源链接： utcz.com/qa/417767.html

回到顶部