Расстояние до ближайшего ненулевого значения в списке?

Question

У меня есть такой список:

[0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1]

, и я хотел бы получить список, который описывает расстояние до ближайшего ненулевого значения для каждого элемента.В этом случае это будет:

[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Answer 1

Вы можете использовать два понимания списка, чтобы собрать расстояния, проходящие вперед и назад по списку:

s = [0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1]

forward = [s[i:].index(1) if x!=1 else 0 for i, x in enumerate(s)]

s_r = s[::-1]

backward = [s_r[i:].index(1) if 1 in s_r[i:] else 0 if x==1 else float('inf') for i, x in enumerate(s_r)][::-1]

Затем вы можете сжать два результирующих списка вместе и взять минимальное расстояние для каждого индекса:

final = [min(i,j) for i, j in zip(forward, backward)]

Выход:

[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Answer 2

1. Инициализировать список расстояний бесконечностью.

2. Зацикливать список и отслеживать расстояние до последнего ненулевого значения.Если расстояние меньше, чем расстояние, сохраненное в списке (в настоящее время бесконечность), обновите список distances.

3. Повторите шаг 2, но выполните итерацию по списку в обратном порядке.

Код:

lst = [0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1]

# initialize the distances to infinity
distances = [float('inf')] * len(lst)

# loop over the list twice, once from the left and once from the right
for indices in [range(len(lst)), range(len(lst)-1, -1, -1)]:
    # keep track of the distance to the last seen non-zero value
    distance = float('inf')

    for i in indices:
        # when we find a non-zero value, set the distance to 0
        if lst[i] != 0:
            distance = 0

        distances[i] = min(distances[i], distance)

        # with each step we take, increase the distance by 1
        distance += 1

print(distances)
# output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Answer 3

import numpy as np 
test = [0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1]
non_zero_idx = np.array([idx for idx, x in enumerate(test) if x is not 0])

В этот момент у вас есть idx всех значений, которые не равны нулю.Все, что вам нужно сделать, это взять минимум между разницей этого и idx значения для каждого значения.

distances = [min(abs(idx-np.array(non_zero_idx))) for idx, x in enumerate(test)]
distances

[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Answer 4

def f(lst):
    ans = [0 for x in range(len(lst))]
    last_non_zero = -len(lst)
    last_edited = -1
    for i in range(len(lst)):
        if lst[i] != 1:
            for j in range(last_edited+1, i):
                ans[j] = min(abs(i-j), abs(j-last_non_zero))
            last_edited = i
            last_non_zero = i
    return ans

Сложность по времени O (n).