Расстояния до нуля

@CDRV · Регистрация: 23.11.2019

Студворк — интернет-сервис помощи студентам

Задан массив a₀,a₁,…,a_n−1. Для каждого элемента найдите расстояние от него до ближайшего нуля. Гарантируется, что в массиве встречается ноль хотя бы один раз.

Входные данные
В первой строке входных данных содержится целое число n (1≤n≤2⋅10⁵) — длина массива a. Вторая строка содержит элементы массива, записанные через пробел (−10⁹≤aⁱ≤10⁹).

Выходные данные
Выведите последовательность d₀,d₁,…,d_n−1. Значение di должно быть равно расстоянию от элемента в позиции i до ближайшего элемента, равного нулю.

Примеры
входные данные
9
2 1 0 3 0 0 3 2 4
выходные данные
2 1 0 1 0 0 1 2 3

входные данные
5
0 1 2 3 4
выходные данные
0 1 2 3 4

входные данные
7
5 6 0 1 -2 3 4
выходные данные
2 1 0 1 2 3 4

@eaa · 11.01.2020, 22:44

Сообщение от Рыжий Лис

хоть один бы человек поинтересовался, каким алгоритмом решается задача и зачем вообще предварительно считать zeros

И зачем предварительно считать zeros, если это не нужно?
А алгоритм простой 2 прохода по массиву, O(n) по времени.

Рыжий Лис · 12.01.2020, 07:41

Чтобы уменьшить число итераций?

Если можете предложить другой алгоритм проще, welcome!

@CDRV · 12.01.2020, 08:53 **[ТС]**

Python
1
2
3
4
5
6
7
zeros = []
for i in range(len(ls)):
    if ls[i] == 0:
        zeros.append(i)
zeros = [i for i, v in range (len(ls)) if v == 0]
 
print(*[min(abs(i - j) for j in zeros) for i in range (len (ls))])

В итоге так получается или нет?

@eaa · 12.01.2020, 13:21

Сообщение от Рыжий Лис

Если можете предложить другой алгоритм проще, welcome!

Дано:

Code
1
A= 1 2 0 2 0 3 4 0 0 3 2 3 4 0 3 2

Ответом будет массив D:

Code
1
D= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Находим индекс левого НУЛЯ,

Code
1
2
A= 1 2 0 2 0 3 4 0 0 3 2 3 4 0 3 2
       ^

заполняем D начиная с него до конца (шаг +1) по следующему правилу:
если A[i] = 0, то D[i] = 0 иначе D[i] = D[i-1] + 1

Code
1
D = 0 0 0 1 0 1 2 0 0 1 2 3 4 0 1 2

Находим индекс правого НУЛЯ,

Code
1
2
A= 1 2 0 2 0 3 4 0 0 3 2 3 4 0 3 2
                             ^

заполняем D начиная с него до индекса левого НУЛЯ (шаг -1) по следующему правилу:
если A[i] = 0, то D[i] = 0 иначе D[i] = min(D[i], D[i+1] + 1)

Code
1
D= 0 0 0 1 0 1 1 0 0 1 2 2 1 0 1 2

заполняем D начиная с индекса левого НУЛЯ до начала (шаг -1) по следующему правилу:
если D[i] = D[i+1] + 1

Code
1
D= 2 1 0 1 0 1 1 0 0 1 2 2 1 0 1 2

Два прохода по массиву A, в итоге сложность O(n)

Рыжий Лис · 12.01.2020, 13:41

Вроде, проще, чем у меня. Я сохранял индексы нулей, а потом считал расстояния до всех. O(N*M), где M-количество нулей.

@_rus · 01.08.2022, 23:04

eaa, Скажите пожалуйста, как называется этот алгоритм? Хочу изучить поподробнее

@Red white socks · 02.08.2022, 08:34

_rus, этот алгоритм называется мозг)

Новые блоги и статьи Все статьи Все блоги /
сукцессия 33. открытые вопросы от клауде anaschu 19.07.2026 "Что накопилось за эту часть А — тринадцать правок, из которых шесть пришли из ваших вопросов и каждая оказалась реальной ошибкой, а не калибровкой: односторонний симбиоз, отсутствующий листопад,. . .	32 сукцессия anaschu 19.07.2026 сукцессия 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не «подкручивает» сходимость —. . .	сукцессия 31: модель микоризы - это модель ещё нескольких явлений, социальных и экономических anaschu 18.07.2026 Теория «Всего»: апдейт v1. 1. 2 — 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не. . .	сукцессия 30. Массив проверяющих друг друга моделей anaschu 18.07.2026 Архитектура сети взаимопроверяющих моделей микоризной сукцессии (v2. 0) Развитие тензорного ОДУ-ядра и создание кросс-платформенного калибровочного полигона Уважаемые коллеги! В продолжение. . .
Грибы - это женщины, деревья - это мужчины. Анти инь янь для союза мужчины и женщины. anaschu 18.07.2026 ГЛАВНЫЙ НАУЧНО-ФИЛОСОФСКИЙ ВЫВОД: Сексуально-Репродуктивный Капитализм против Государства Моногамии Коллеги, мы вышли на финишную прямую 20-мерного ОДУ-моделирования вековой сукцессии (ветка. . .	Текстовый слайдер с нумерацией страниц и кроссбраузерность. russiannick 18.07.2026 Один мой друг написал текстовый слайдер с нумерацией страниц. Сегодня я расскажу как он умудрился подружить его с кроссбраузерностью. Очевидно сложно угодить с шириной каждому браузеру. Один крадет. . .	Грибы - это мемы, дерево - это человек. Применение микоризной модели к теории меметики Докинза. anaschu 18.07.2026 Меметический изоморфизм теории «всего»: Грибная сукцессия как модель эволюции идей Докинза Базовый код системы ОДУ микоризной сукцессии описывает не просто биологию, а универсальную. . .	Грибы - это корпорации, деревья - это государства. Механизм массонского захвата власти anaschu 18.07.2026 Макроэкономический изоморфизм теории «всего»: Грибная сукцессия как модель транснационального капитализма Базовый код системы ОДУ микоризной сукцессии описывает не просто биологию, а. . .

@CDRV 0 / 0 / 0 Регистрация: 23.11.2019 Сообщений: 71

	Расстояния до нуля 27.12.2019, 18:57. Показов 18600. Ответов 26 Метки python, python 3, python 3.7, python 3.x, алгоритм 2, питон, программа (Все метки) Задан массив a₀,a₁,…,a_n−1. Для каждого элемента найдите расстояние от него до ближайшего нуля. Гарантируется, что в массиве встречается ноль хотя бы один раз. Входные данные В первой строке входных данных содержится целое число n (1≤n≤2⋅10⁵) — длина массива a. Вторая строка содержит элементы массива, записанные через пробел (−10⁹≤aⁱ≤10⁹). Выходные данные Выведите последовательность d₀,d₁,…,d_n−1. Значение di должно быть равно расстоянию от элемента в позиции i до ближайшего элемента, равного нулю. Примеры входные данные 9 2 1 0 3 0 0 3 2 4 выходные данные 2 1 0 1 0 0 1 2 3 входные данные 5 0 1 2 3 4 выходные данные 0 1 2 3 4 входные данные 7 5 6 0 1 -2 3 4 выходные данные 2 1 0 1 2 3 4 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	12.01.2020, 07:41
	Чтобы уменьшить число итераций? Если можете предложить другой алгоритм проще, welcome! 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	12.01.2020, 13:41
	Вроде, проще, чем у меня. Я сохранял индексы нулей, а потом считал расстояния до всех. O(N*M), где M-количество нулей. 0

@_rus 0 / 0 / 0 Регистрация: 01.08.2022 Сообщений: 1
	01.08.2022, 23:04
	eaa, Скажите пожалуйста, как называется этот алгоритм? Хочу изучить поподробнее 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	02.08.2022, 08:34
	_rus, этот алгоритм называется мозг) 1