找到最长的连续子数组（未排序）-Python

Question

在上面的列表中，v=[1,2,3,11,5,8,9,10,11,6,4]，其中1、2、3是连续数字（第一个连续集合），8、9、10、11是连续数字（第二个集合，最大的一个）。我该如何找到这第二个集合？下面的代码可以给出连续数字：

for i in range(len(v)-1):
    if v[i+1]==v[i]+1:
        if v[i-1]!=v[i]-1:
             print(v[i])
        print(v[i]+1)

Output:1,2,3,8,9,10,11

我在考虑使用类似以下的东西，将输出添加到一个新的列表中，然后找出该列表的最大值。我想不出将这两个想法结合起来的逻辑。

for i in range(len(v)-1):
    for j in range(i+1,len(v)):
        if v[j]-v[i]  

我看了这个例子，但我觉得那种解决方案与我想要的不同。提前感谢您的时间和建议。

- Sheikh Rahman

---

你想要一个使用你尝试过的概念的解决方案，还是任何解决方案都可以？ - gmds

有什么不太复杂的编程内容（如果可能，像lambda表达式之类的）。谢谢。 - Sheikh Rahman

Answer 1

你可以迭代遍历列表，并将项附加到可能是最长连续子列表的末尾，如果该项与子列表的最后一项不连续，则开始一个新的子列表，并且如果该子列表比当前最长子列表更长，则将其指定为新的最长子列表："最初的回答"。

candidate = []
longest = []
for i in v:
    if candidate and candidate[-1] != i - 1:
        if len(candidate) > len(longest):
            longest = candidate
        candidate = []
    candidate.append(i)
if len(candidate) > len(longest):
    longest = candidate

longest becomes:

[8, 9, 10, 11]

- blhsing

Answer 2

你的答案已经很接近正确了。将当前运行作为列表存储，必要时更新最佳列表，并在中断运行时清除它。如果最后一组出现在列表的末尾，则应注意包括它。"Original Answer"翻译成"最初的回答"。

v = [1,2,3,11,5,8,9,10,11,6,4]
best = []
run = []

for i in range(1, len(v) + 1):
    run.append(v[i-1])

    if i == len(v) or v[i-1] + 1 != v[i]:
        if len(best) < len(run):
            best = run

        run = []

print(best)

输出：

[8, 9, 10, 11]

- ggorlen

Answer 3

您可以使用滑动窗口来缩小大小并检查所有数字是否按升序排列：

from itertools import islice

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result


def longestConsecutiveSeq(s):
  for seq in (window(s, i) for i in range(len(s)-1, 1, -1)):
    for subseq in seq:
      l = list(subseq)
      if all((y-x) == 1 for (x, y) in zip(l, l[1:])):
        return l

print(longestConsecutiveSeq([1,2,3,11,5,8,9,10,11,6,4]))

结果：[8, 9, 10, 11]

这个算法将在第一次遇到最大尺寸时停止。

- Netwave

Answer 4

你可以使用pandas：

import pandas as pd

v=[1,2,3,11,5,8,9,10,11,6,4]

s = pd.Series(v)

sgc = s.groupby(s.diff().ne(1).cumsum()).transform('count')

result = s[sgc == sgc.max()].tolist()

result

输出：

[8, 9, 10, 11]

细节：

创建一个pandas系列，使用diff计算与前一个值的差异。接下来，使用ne创建一个布尔系列，其中差异不等于1，然后使用cumsum这个布尔系列来创建组，其中连续的值都被分组在一起。使用groupby和transform将每个记录的组大小计数。最后，使用布尔索引仅选择系列中组中计数等于所有组的最大计数的部分。然后使用tolist转换为数组。

- Scott Boston

Answer 5

您可以使用元素和它们的索引之间的差异来使用函数“groupby()”对元素进行分组：

from itertools import groupby

l = [1, 2, 3, 11, 5, 8, 9, 10, 11, 6, 4]

gb = groupby(enumerate(l), lambda x: x[0] - x[1])
max(([i for _, i in g] for _, g in gb), key=len)
# [8, 9, 10, 11]

- Mykola Zotko