Ctrl K

Расстояния до двойников

Средняя
Дан массив labels. Для каждой позиции i посчитайте сумму расстояний |i − j| до всех других позиций j, где стоит такое же значение. Если таких позиций нет, сумма равна 0. Верните массив этих сумм той же длины, что и labels. Перебор всех пар — O(n²); нужно быстрее.
Пример 1
labels=[7, 2, 7, 2, 7] → [6, 2, 4, 2, 6]

Семёрки стоят на позициях 0, 2, 4: для позиции 0 это 2 + 4 = 6, для 2 — 2 + 2 = 4, для 4 — 4 + 2 = 6. Двойки на позициях 1 и 3 отстоят друг от друга на 2. Ответ [6, 2, 4, 2, 6].

Пример 2
labels=[9, 8] → [0, 0]

Пар нет, у каждого элемента 0.

Пример 3
labels=[0, 0, 0] → [3, 2, 3]
Ограничения
  • 1 ≤ len(labels) ≤ 10⁵
  • 0 ≤ labels[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый длинный отрезок с заданной суммой СредняяОтрезок с суммой, кратной делителю СредняяПоровну орлов и решек СредняяОтрезки с заданной суммой СредняяОкна с заданным числом тревог Средняя
загружаем Python…
Вход
labels=[7, 2, 7, 2, 7]
Ожидается
[6, 2, 4, 2, 6]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 108 тестов на сервере, включая скрытые.