例如，如果我有一个列表
[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的解决方案，因为算法才是重要的。
谢谢。
如何在一个列表中找到不一定相邻的最大连续数字集合？
12
- dangerChihuahua007
8
10个回答
15
以下是一个简单的一遍 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)
- Raymond Hettinger
7
@RaymondHettinger - 最后一行应该是：
print range(maxend-maxrun+1, maxend+1)吗？否则对于s = [1,4,2,3,5,4,9,10,11,5,6,7,8,1,3,4,5]，我只得到了[4, 5, 6, 7, 8]，而不是[1, 2, 3, 4, 5, 6, 7, 8]。 - PaulMcG@Paul McGuire，同意，我认为它应该是maxrun而不是run。 - sunqiang
这个解决方案只在数据已排序的情况下有效。也就是说，它不考虑 1、2、3、5、6、7、8、4 这样的数据。如果最后输入的是 4，则不会更新值为 5、6、7、8 的数据。因此，除非将排序复杂度考虑在内，否则其并非 O(n)。 - Brett Stottlemyer
@Raymond 好的，我会接受我的解释不是 OP 感兴趣的内容，并撤销我的踩票。希望这不会让其他人误以为这是找到最长序列而不是最长上升序列的解决方案。 - Brett Stottlemyer
@RaymondHettinger 抱歉，我以为我可以在不编辑的情况下取消我的踩。但是 Stack Overflow 不允许我这样做。 - Brett Stottlemyer
显示剩余2条评论
3
虽然不是很聪明，也不能达到O(n)的复杂度，但还是可以进行一些优化。但它能够正常工作。
def longest(seq):
result = []
for v in seq:
for l in result:
if v == l[-1] + 1:
l.append(v)
else:
result.append([v])
return max(result, key=len)
- Ignacio Vazquez-Abrams
3
实际上，这个问题没有O(n)的解决方案 :-) - Abhijit
这是O(n^2)的，我的也是。需要考虑不同的方法。 - jeffknupp
1@Abhijit：有的，看看Raymond Hettinger的。 - orlp
2
您可以使用Patience Sort实现最长递增子序列算法。
这是测试结果。
复杂度的阶数为O(nlogn)。
在维基链接中有一个注释声称，通过依靠Van Emde Boas树，可以达到O(n.loglogn)。
def LargAscSub(seq):
deck = []
for x in seq:
newDeck = [x]
i = bisect.bisect_left(deck, newDeck)
deck[i].insert(0, x) if i != len(deck) else deck.append(newDeck)
return [p[0] for p in deck]
这是测试结果。
>>> LargAscSub([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]
>>> LargAscSub([1, 2, 3, 11, 12, 13, 14])
[1, 2, 3, 11, 12, 13, 14]
>>> LargAscSub([11,12,13,14])
[11, 12, 13, 14]
复杂度的阶数为O(nlogn)。
在维基链接中有一个注释声称，通过依靠Van Emde Boas树，可以达到O(n.loglogn)。
- Abhijit
3
2结果不必是连续整数吗？ - srgerg
@srgerg，请查看Serdalis提出的上述评论问题和Chi Zeng的回复。 - Abhijit
不是最大的升序，而是最大的连续升序。 - jeffknupp
1
使用修改过的基数排序如何？正如JanneKarila所指出的，该解决方案不是O(n)。它使用基数排序，维基百科表示：对于具有k个或更少位数的n个键，基数排序的效率为O(k·n)。
这只有在您知道我们正在处理的数字范围时才能起作用，因此这将是第一步。
查找起始列表中的每个元素，找到最低值
l和最高值h。在这种情况下，l是1，h是11。请注意，如果您已经出于某种原因知道了某个范围，则可以跳过此步骤。创建一个结果列表，其大小与我们的范围相同，并将每个元素设置为 null。
查看列表中的每个元素，并在需要时将它们添加到结果列表的适当位置。例如，如果元素是 4，则在位置 4 上将 4 添加到结果列表中。
result[element] = starting_list[element]。如果您想要丢弃重复项，可以这样做，它们将被覆盖。遍历结果列表以查找没有任何 null 值的最长序列。保持一个
element_counter，以知道我们正在查看结果列表中的哪个元素。保持一个curr_start_element，设置为当前序列的开始元素，并保持当前序列的长度curr_len。还要保持一个longest_start_element和一个 `longest_len'，它们最初为零，并随着我们遍历列表而更新。返回从
longest_start_element开始并取longest_len的结果列表。
编辑：已添加代码。测试通过
#note this doesn't work with negative numbers
#it's certainly possible to write this to work with negatives
# but the code is a bit hairier
import sys
def findLongestSequence(lst):
#step 1
high = -sys.maxint - 1
for num in lst:
if num > high:
high = num
#step 2
result = [None]*(high+1)
#step 3
for num in lst:
result[num] = num
#step 4
curr_start_element = 0
curr_len = 0
longest_start_element = -1
longest_len = -1
for element_counter in range(len(result)):
if result[element_counter] == None:
if curr_len > longest_len:
longest_start_element = curr_start_element
longest_len = curr_len
curr_len = 0
curr_start_element = -1
elif curr_start_element == -1:
curr_start_element = element_counter
curr_len += 1
#just in case the last element makes the longest
if curr_len > longest_len:
longest_start_element = curr_start_element
longest_len = curr_len
#step 5
return result[longest_start_element:longest_start_element + longest_len-1]
- jb.
4
第4步对结果列表进行n次迭代，因此这不是O(n)。 - jeffknupp
@jknupp 不需要多次遍历，只需要一次即可。这与从列表中查找最大值相同，只不过它在列表中查找最长的序列。假设列表为
[1,2,3,null,5,6,7,8,null,10]，我发现[1,2,3]的长度为3，因此我保存起始索引。然后看到[5,6,7,8]的长度为4，因此更新最长索引/长度变量。[8]不会改变它。一个循环，找到了最长的序列。 - jb.O(n) 中的 n 指的是输入列表的大小。值的范围可以远远大于列表的长度，并且与其无关。 - Janne Karila
@JanneKarila，我的错误，你是对的。根据维基百科，“基数排序的效率为O(k·n)，其中n个键具有k位或更少的数字。” - jb.
0
如果结果确实必须是连续升序整数的子序列，而不仅仅是升序整数，那么在确定最长子序列之前，没有必要记住每个完整的连续子序列，你只需要记住每个子序列的起始和结束值。因此，你可以像这样做：
def longestConsecutiveSequence(sequence):
# map starting values to largest ending value so far
map = collections.OrderedDict()
for i in sequence:
found = False
for k, v in map.iteritems():
if i == v:
map[k] += 1
found = True
if not found and i not in map:
map[i] = i + 1
return xrange(*max(map.iteritems(), key=lambda i: i[1] - i[0]))
如果我在原始样本日期上运行此代码（即
[1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]），我会得到：>>> print list(longestConsecutiveSequence([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]
如果我在Abhijit的样本之一
[1,2,3,11,12,13,14]上运行它，我会得到：>>> print list(longestConsecutiveSequence([1,2,3,11,12,13,14]))
[11, 12, 13, 14]
遗憾的是，这个算法在最坏情况下的时间复杂度为 O(n*n)。
- srgerg
0
警告：这是一种欺骗性的方法（也就是我使用Python...）
import operator as op
import itertools as it
def longestSequence(data):
longest = []
for k, g in it.groupby(enumerate(set(data)), lambda(i, y):i-y):
thisGroup = map(op.itemgetter(1), g)
if len(thisGroup) > len(longest):
longest = thisGroup
return longest
longestSequence([1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11, 15,15,16,17,25])
- odgrim
0
你需要了解最大连续和(最优子结构)：
def msum2(a):
bounds, s, t, j = (0,0), -float('infinity'), 0, 0
for i in range(len(a)):
t = t + a[i]
if t > s: bounds, s = (j, i+1), t
if t < 0: t, j = 0, i+1
return (s, bounds)
这是动态规划的一个例子，时间复杂度为O(N)
- Keldon Alleyne
0
O(n)的解决方案即使序列不从第一个元素开始也可以工作。
警告：如果len(A)=0，则无法工作。
A = [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]
def pre_process(A):
Last = {}
Arrow = []
Length = []
ArgMax = 0
Max = 0
for i in xrange(len(A)):
Arrow.append(i)
Length.append(0)
if A[i] - 1 in Last:
Aux = Last[A[i] - 1]
Arrow[i] = Aux
Length[i] = Length[Aux] + 1
Last[A[i]] = i
if Length[i] > Max:
ArgMax = i
Max = Length[i]
return (Arrow,ArgMax)
(Arr,Start) = pre_process(A)
Old = Arr[Start]
ToRev = []
while 1:
ToRev.append(A[Start])
if Old == Start:
break
Start = Old
New = Arr[Start]
Old = New
ToRev.reverse()
print ToRev
欢迎Python化!!
- jimifiki
0
好的，这是另一次在Python中的尝试：
def popper(l):
listHolders = []
pos = 0
while l:
appended = False
item = l.pop()
for holder in listHolders:
if item == holder[-1][0]-1:
appended = True
holder.append((item, pos))
if not appended:
pos += 1
listHolders.append([(item, pos)])
longest = []
for holder in listHolders:
try:
if (holder[0][0] < longest[-1][0]) and (holder[0][1] > longest[-1][1]):
longest.extend(holder)
except:
pass
if len(holder) > len(longest):
longest = holder
longest.reverse()
return [x[0] for x in longest]
示例输入和输出：
>>> demo = list(range(50))
>>> shuffle(demo)
>>> demo
[40, 19, 24, 5, 48, 36, 23, 43, 14, 35, 18, 21, 11, 7, 34, 16, 38, 25, 46, 27, 26, 29, 41, 8, 31, 1, 33, 2, 13, 6, 44, 22, 17,
12, 39, 9, 49, 3, 42, 37, 30, 10, 47, 20, 4, 0, 28, 32, 45, 15]
>>> popper(demo)
[1, 2, 3, 4]
>>> demo = [1,4,2,3,5,4,5,6,7,8,1,3,4,5,9,10,11]
>>> popper(demo)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>>
- Spencer Rathbun
-2
这应该可以解决问题（而且是O(n)）：
target = 1
result = []
for x in list:
for y in result:
if y[0] == target:
y[0] += 1
result.append(x)
对于任何起始数字，这个方法都有效：
result = []
for x in mylist:
matched = False
for y in result:
if y[0] == x:
matched = True
y[0] += 1
y.append(x)
if not matched:
result.append([x+1, x])
return max(result, key=len)[1:]
- jeffknupp
20
5这将找到以1开头的第一个元素，而不是最大的元素。
[2, 3, 4, 5, 1, 2] - Ignacio Vazquez-Abrams1为什么您或者点赞者不检查一下代码？第一次如何订阅
y？(TypeError: 'int' object is unsubscriptable) - joaquin1第一个代码示例返回一个空列表，而第二个在
if y[0] == x行引发了TypeError：'int' object is not subscriptable。 - David Z1还有
False应该大写，但在运行之前我已经修复了它。 - David Z@jb。正如我在问题中所评论的那样，我甚至不确定正确的行为是什么，因此在等待OP澄清之前，我无法告诉您您的算法是否正确。此外，我认为我没有时间解析算法的书面描述。提供示例代码将使测试更容易。 - David Z
显示剩余15条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
[1,2,3,4,5,6,7,8,9,10,11]。我看不出来这些数字不被包括的原因，因为它们不必是相邻的。 - Serdalis[5,3,6,10,13,5,2,11,15,8,15]，预期结果是什么？或者[7,6,5,4,1,2,3]？ - David Z