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

@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, этот алгоритм называется мозг)

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

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

	Расстояния до нуля 27.12.2019, 18:57. Показов 18693. Ответов 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