0

Прохожу курсы по Python, стоит задача по поиску расстояния до ближайшего нуля.

Вводные данные (пример):

5 # кол-во элементов
0 1 4 9 0

А должно быть:

0 1 2 1 0

Задачу я решил, но при прохождении тестов, где программу нагружают по-максимум, она валится из-за ограничении памяти. Т.е. надо как-то оптимизировать мой код, но как - ума не приложу.

street = int(input())
land_number = input().split()

f = []

zero_number = [k for k, v in enumerate(land_number) if v == '0']

for i in range(len(zero_number)):
    left = list(reversed(range(0, len(land_number[:zero_number[i]:]) + 1)))
    right = list((range(1, len(land_number[zero_number[i] + 1:]) + 1)))
    f.append(left + right)
print(*map(min, zip(*f)))
5
  • 3
    Возможный дубликат вопроса: Расстояния до нуля
    – Jack_oS
    23 июн 2021 в 8:01
  • А какие ограничения в задаче? И можно ли получить доступ к тестирующей системе? А вообще, у вас алгоритм квадратный как по времени, так и по памяти, поэтому не думаю, что его можно ускорить без значительных изменений. Например, можно для i-того нуля минимизировать не все расстояния, а только те, которые находятся между (i-1)-ым и (i+1)-ым нулями. Но тогда всю внутренность вашего цикла нужно полностью менять, а ведь это и есть основа вашего алгоритма.
    – EzikBro
    23 июн 2021 в 8:14
  • Но чтобы оптимизировать именно по памяти рекомендую вместо f = [] использовать ans = [street] * street, вместо f.append() использовать ans = list(map(min, zip(ans, left+right))) и соответственно в конце выводить с помощью print(*ans). Таким образом, память получается линейная, хоть скорость и оставляет желать лучшего
    – EzikBro
    23 июн 2021 в 8:22
  • Спасибо. Все как вы сказали - по памяти стало ок, но программа возникли проблемы со скоростью) К сожалению, к тест-системе доступ только у студентов курса ( 23 июн 2021 в 9:25
  • В итоге код пришлось переписать полностью и тесты пролезли. Спасибо EzikBro! 23 июн 2021 в 14:15

1 ответ 1

1

Вот за 2 прохода по списку туда-обратно:

data = [0, 1, 4, 9, 0]
res = [0] * len(data)

i_zero_first = i_zero_last = data.index(0)
for i in range(i_zero_first, len(data)):
    if data[i] != 0:
        res[i] = res[i-1] + 1
    else:
        i_zero_last = i

for i in range(i_zero_last, i_zero_first, -1):
    res[i] = 0 if data[i] == 0 else min(res[i], res[i+1] + 1)

for i in range(i_zero_first-1, -1, -1):
    res[i] = res[i+1] + 1

print(res)

В принципе, тут даже второй список не нужен. Если входные данные больше не представляют ценности, то можно проводить все манипуляции прямо в над исходным списком.

1
  • Спасибо за ваше решение) воспользуюсь, если свой не смогу исправить ( пока хотелось как-то оптимизировать свой код, если это возможно 22 июн 2021 в 20:56

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.