0

Имеется код алгоритма нахождения ближайшего нуля:

def nearest_zero(distance):
    zeros = [float('inf')] * len(distance)
    first, last = distance.index(0), distance[::-1].index(0)
    for i in range(first, len(distance), +1):
        if distance[i] == 0:
            zeros[i] = 0
        else:
            zeros[i] = zeros[i-1] + 1
    for i in range(len(distance)-last-1, first, -1):
        if distance[i] == 0:
            zeros[i] = 0
        else:
            zeros[i] = min(zeros[i], zeros[i + 1] + 1)
    for i in range(first - 1, -1, -1):
        zeros[i] = zeros[i + 1] + 1
    return zeros

В нем есть дублирующиеся куски

        if distance[i] == 0:
            zeros[i] = 0

мне нужно объединить код в один цикл вроде:

for i in ... range(first_zero, len(distance), +1), range(len(distance)-last_zero-1, first_zero, -1):
        if distance[i] == 0:
            zeros[i] = 0

но проблема в том, что условие под вторым else:

        else:
            zeros[i] = min(zeros[i], zeros[i + 1] + 1)

зависит от полного выполнения первого цикла:

    for i in range(first, len(distance), +1):
        if distance[i] == 0:
            zeros[i] = 0
        else:
            zeros[i] = zeros[i-1] + 1

и я не могу понять как это возможно реализовать.

3
  • Ну, несколько range() в один for объединить то можно: for x in ( *range(), *range() ). Только в вашем случае встаёт вопрос - зачем?
    – GrAnd
    9 апр 2021 в 20:13
  • Изучаю python Это замечание ревьюера, вот дословно: В методе есть некоторое дублирование кода в циклах. Предлагаю организовать один цикл for i in ... range(first_zero, len(distance), +1), range(len(distance)-last_zero-1, first_zero, -1):
    – ddwarf
    9 апр 2021 в 20:16
  • Странный ревьюер. :) Тела циклов же разные. В одном цикле будет только ненужное усложнение кода и потеря читабельности. Если хочется, то можно заменить if ... else одной строкой: zeros[i] = zeros[i-1] + 1 if distance[i] != 0 else 0 (ну и для второго цикла по аналогии). Строчка будет одна и она будет отличаться в разных циклах.
    – GrAnd
    9 апр 2021 в 20:21

2 ответа 2

0

Оба цикла можно объединить в один. При первом проходе условие в операторе if k < dists[i]: всегда истинно и его хочется убрать, но ради объединения двух проходов оставим как есть. Это упрощает код концептуально: начинаете с прямоугольного бруска достаточной высоты, на первом проходе обрезаете значения пилой направо, на втором - пилой налево:

 1  1  0  1  1  1  1  0  1  1  1  1  1  0  1  1  1 
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17  исходный массив
17 17  0  1  2  3  4  0  1  2  3  4  5  0  1  2  3  пила направо
 2  1  0  1  2  2  1  0  1  2  3  2  1  0  1  2  3  пила налево
def nearest_zeros(values):
    n = len(values)
    dists = [n] * n

    for r in (range(n), reversed(range(n))):
        k = len(values)
        for i in r:
            if values[i] == 0:
                k = 0
            else:
                k += 1
            if k < dists[i]:
                dists[i] = k

    return dists
1
  • Большое спасибо, думаю ваша реализация это то что нужно!
    – ddwarf
    9 апр 2021 в 22:09
0

Вот еще предложили хорошее рабочее решение.

from itertools import chain

def nearest_zero(values):
    sequence = [float("inf")] * len(values)
    cnt = sequence[0]
    for i in chain(range(len(values)), range(len(values) - 1, -1, -1)):
        if values[i] == 0:
            cnt = 0
        sequence[i] = min(sequence[i], cnt)
        cnt += 1
    return sequence

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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