#python #python-3.x #python-2.7
#python #python-3.x #python-2.7
Вопрос:
Я написал код для получения неубывающей подпоследовательности из списка python
lis = [3, 6, 3, 8, 6, 4, 2, 9, 5]
ind = 0
newlis = []
while ind < len(lis):
minele = min(lis[ind:])
newlis.append(minele)
ind = lis.index(minele) 1
print(newlis)
Хотя кажется, что это нормально работает с тестовыми примерами, которые я пробовал, есть ли более эффективный способ сделать это, потому что наихудшая временная сложность приведения этого кода равна O (n ^ 2) для случая, когда список уже отсортирован, предполагая, что встроенный метод min использует линейный поиск.
Чтобы быть более точным, мне нужен максимально длинный неубывающий вложенный список, и вложенный список должен начинаться с минимального элемента списка. И под вложенным списком я подразумеваю, что элементы не обязательно должны находиться в непрерывном отрезке в данном исходном списке (lis).
Комментарии:
1. Ваш код выводит
[2, 5]последнюю встречающуюся неубывающую подпоследовательность. Можете ли вы объяснить, какая неубывающая подпоследовательность должна быть результатом? Вам нужна самая длинная подпоследовательность, или все из них, или подойдет любая из них? Самую длинную подпоследовательность можно найти за O (n log n) времени.2.
[2,5]выводимое значение не существует в вашем списке.3. похоже, что этот код просто переходит к следующему наименьшему элементу в оставшемся списке и добавляет его в список. итак, что именно вы подразумеваете под подпоследовательностью
4. Я предполагаю, что OP означает несмежную подпоследовательность, глядя на их код.
5. @Jarek. D отредактировал вопрос
Ответ №1:
Я почти убежден, что он может выполняться за линейное время. Вам просто нужно продолжать пытаться построить самую длинную последовательность во время одного сканирования и либо сохранить их все, как я сделал, либо сохранить самую длинную в данный момент.
lis = [9, 1, 3, 8, 9, 6, 9, 8, 2, 3, 4, 5]
newlis = [[]]
minele = min(lis)
ind = lis.index(minele)
currmin = minele
seq = 0
longest = 0
longest_idx = None
while ind < len(lis):
if lis[ind] >= currmin:
newlis[seq].append(lis[ind])
currmin = lis[ind]
ind = 1
else:
if len(newlis[seq]) > longest:
longest = len(newlis[seq])
longest_idx = seq
newlis.append([minele])
currmin = minele
seq = 1
if len(newlis[seq]) > longest:
longest = len(newlis[seq])
longest_idx = seq
print(newlis)
print(newlis[longest_idx])
Комментарии:
1. Попробуйте с
lis = [6, 0, 8, 1, 3, 6, 2, 5, 9, 4, 8]. Самой длинной подпоследовательностью должна быть[0, 1, 3, 5, 8], но код находит только подпоследовательности длиной 4 и меньше. Можно ли это исправить? Я все еще думаю, что общее решение требует O (n log n) времени.2. Верно, это проблема. Но, возможно, это можно было бы исправить за счет некоторой сложности памяти. Я мог бы сохранить все возможные собранные подпоследовательности отдельно (например, [0,1], [0,1,3]), а затем после разрыва последовательности попытаться объединить новый локальный минимум с самой длинной предыдущей подпоследовательностью, максимальное значение которой меньше или равно текущему новому минимуму. Просто идея, не уверен, насколько оптимальна для больших последовательностей, но в принципе это все равно должно быть выборочное сканирование с некоторым дополнительным временем, пропорциональным количеству собранных в данный момент последовательностей. Так что на самом деле не O (n), но, возможно, лучше, чем O (n logn)
3. Я ценю время и усилия каждого. Я думаю, что мне не удалось объяснить, что именно я хотел. Не удается придать проблеме больше контекста (что, возможно, могло бы внести больше ясности) Я стремлюсь решить по определенным причинам.