DjangoBB LoFi version

Полная версия: Задача №3850. Сжатие списка

Начало » Центр помощи » Задача №3850. Сжатие списка

Fiares_Curie

Окт. 13, 2021 21:09:53

Дан список целых чисел. Требуется “сжать” его, переместив все ненулевые элементы в левую часть списка, не меняя их порядок, а все нули - в правую часть. Порядок ненулевых элементов изменять нельзя, дополнительный список использовать нельзя, задачу нужно выполнить за один проход по списку. Распечатайте полученный список.

Входные данные:

Вводится список чисел. Все числа списка находятся на одной строке.

Выходные данные:

Выведите ответ на задачу.

Мой код:

 s = list(map(int,input().split()))
for i in range(len(s)-1, -1, -1):
    if s[i] == 0:
        s.append(s.pop(i))
print(*s)

Но на одном из тестов мне выводит “Превышено максимальное время работы”. Почему так?

doza_and

Окт. 13, 2021 22:20:16

Fiares_Curie
Почему так?

Не знаю.
Но есть гипотеза. Трудоемкость pop O(n) Где n длина списка. Поэтому у вас трудоемкость порядка n^2 А можно было сделать n.

py.user.next

Окт. 13, 2021 22:44:06

Fiares_Curie
задачу нужно выполнить за один проход по списку

Вот это признак того, что список может быть бесконечным. На практике это значит, например, что данные списка приходят с какого-то датчика непрерывно и бесконечно и их надо обрабатывать на лету. Оттуда и один проход. Так что, я думаю, они сделали в тестах защиту от вычисления длины списка. Не можешь ты вычислить длину бесконечного списка, повиснет функция вычисления длины. Ну, как бы в теории так, в питоне-то длина списка постоянно перевычисляется при любом изменении списка и хранится в служебном поле (но это неточно). Но по теории, вычисление длины списка имеет временную сложность O(n). Так что надо от этого избавиться.

Иди слева направо и просто удаляй нули и считай их, а в конце допишешь столько нулей, сколько удалил.