Оптимизация программы по поиску пути до ближайшего нуля Python

Question

Прохожу курсы по 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)))

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

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

БЛОГ НА HUSL

Оптимизация программы по поиску пути до ближайшего нуля Python

Ответы (1 шт):