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

Answer 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:] 

Answer 3

您可以使用Patience Sort实施Largest Ascending Sub-sequence Algorithm

的

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] 

复杂的顺序是Ø（nlogn）

有在他们声称可以实现Ø（n.loglogn）维基链接一个音符依靠Van Emde Boas tree

Answer 4

不是那么聪明，不是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) 

Answer 5

如何使用修改Radix Sort？正如JanneKarila指出的解决方案不是O（n）。它使用基数排序，其中维基百科说Radix sort's efficiency is O(k·n) for n keys which have k or fewer digits.

这只会在你知道我们处理的数字范围，所以这将是第一步。

1. 在首发名单找到最低，l和最高的，h数量看每个元素。在这种情况下l为1和h是11。注意，如果你已经知道的范围内由于某些原因，你可以跳过这一步。

2. 创建一个结果列表我们的范围的大小，并将每个元素设置为null。

3. 只看该列表中的每个元素，并根据需要在适当的地方将它们添加到结果列表。即，该元件是一个如图4所示，在位置4 result[element] = starting_list[element]添加4到结果列表中。如果你愿意，你可以丢弃重复的内容，它们只会被覆盖。

4. 通过结果列表中去寻找最长的序列，没有任何空值。保持一个element_counter知道我们要找什么元素在结果列表中。保持curr_start_element设置为当前序列的开始元素，并保持当前序列的长度为curr_len。同时保留一个longest_start_element和一个`longest_len'，它将从零开始，并在我们移动列表时进行更新。

5. 返回结果列表开始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] 

Answer 6

如果结果确实必须的连续上升的整数，而不是仅仅的递增整数子序列，那么就没有必要记住每个完整连续的子序列，直到你确定哪个最长，你只需要记住每个子序列的起始值和结束值。所以，你可以做这样的事情：

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）。

Answer 7

警告：这是cheaty办法做到这一点（又名我使用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]) 

Answer 8

您需要最大连续总和（Optimal Substructure）：

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）

Answer 9

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  

Pythonizations欢迎

警告不起作用!!

Answer 10

好吧，这里的蟒蛇又一次尝试：

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] 
>>>