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

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

Новые блоги и статьи Все статьи Все блоги /
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .	[golang] Worker Pool alhaos 09.06.2026 Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .	Свет внутри себя kumehtar 07.06.2026 Пусть это будет здесь lIs4oanZS9Y	Программа для com-порта Uhbif79 05.06.2026 Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .	Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .

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

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