Например, если у меня есть список
[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)
Не тот умный, а не 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)
Вы можете использовать "Сортировать по терпению" Самый большой восходящий суб- алгоритм последовательности
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)
В ссылке wiki была одна заметка, в которой утверждалось, что вы можете достичь O (n.loglogn), полагаясь на дерево Ван Эмде Боас
Как насчет использования измененного Radix Sort? Как отметила Яннекарила, решение не является O (n). Он использует сортировку Radix, о которой говорит wikipedia Radix sort efficiency is O(k·n) for n keys which have k or fewer digits.
Это будет работать, только если вы знаете диапазон чисел, с которыми мы имеем дело, так что это будет первый шаг.
Посмотрите на каждый элемент в стартовом списке, чтобы найти самый низкий, l и самый высокий, h номер. В этом случае l равно 1 и h равно 11. Примечание. Если вы уже знаете диапазон по какой-либо причине, вы можете пропустить этот шаг.
Создайте список результатов размером нашего диапазона и установите для каждого элемента значение null.
Посмотрите на каждый элемент в списке и добавьте их в список результатов в соответствующем месте, если это необходимо. т.е. элемент равен 4, добавьте 4 в список результатов в позиции 4. result[element] = starting_list[element]. Вы можете выбросить дубликаты, если хотите, они просто будут перезаписаны.
Перейдите в список результатов, чтобы найти самую длинную последовательность без нулевых значений. Сохраните element_counter, чтобы узнать, какой элемент в списке результатов мы просматриваем. Удерживайте curr_start_element в начале элемента текущей последовательности и сохраняйте curr_len, как долго текущая последовательность. Также сохраняйте longest_start_element и `longest_len ', которые начинаются как ноль и обновляются по мере перемещения по списку.
Верните список результатов, начинающийся с longest_start_element и принимающий longest_len
EDIT: добавлен код. Протестировано и работает
#note this doesn't work with negative numbers
#it 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]
Если результат действительно должен быть подпоследовательностью последовательных восходящих целых чисел, а не просто восходящими целыми числами, то нет необходимости помнить каждую целую последовательную подпоследовательность, пока вы не определите, какая из них самая длинная, вам нужно только помнить начальное и конечное значения каждой подпоследовательности. Таким образом, вы можете сделать что-то вроде этого:
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) в худшем случае.
Предупреждение: Это обманный способ сделать это (иначе я использую 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])
Вам нужна Максимальная непрерывная сумма (Оптимальная субструктура):
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)
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:
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]
>>>
Это должно сделать трюк (и есть 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:]