Точка поиска, сумма расстояний которой суммируется со всеми другими точками на линии, является самой низкой

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

Input:
22 // point no 1
35 // point no 2
5  // ...
44
45
20
46

Output: 2 // point with number 2 has got the lowest sum (87)

Я знаю, как это сделать итеративным способом, но я думаю о чем-то более оптимальном.

Ответ 1

Это называется median. Просто отсортируйте значения и выберите центр. Если n четно, любое из двух значений центра будет делать.

Существуют также O (n) алгоритмы для вычисления медианы.

Ответ 2

Ответ: решение median является правильным, однако может быть

Несколько решений

Если существует четное количество точек: p ₁ < & Hellip; p _n < p _{n + 1} < & Hellip; < p _2n, сумма расстояний будет минимальной для любой точки x, где * p _n & le; x & le; p _{n + 1}

Чтобы понять, почему медиана работает, рассмотрите этот

Описание

Скажем, мы имеем n точки, где p _i < p _{я + 1} для всех применимых i.

Будучи наивным, мы можем подумать, что x = p ₁ - лучший выбор для минимизации суммы S. Увеличение x на единицу, что происходит с суммой S? Мы находимся дальше от p ₁, но 1 ближе ко всем другим точкам.

Таким образом, S _{p ₁ + 1}= S _{p ₁} + 1 - (n - 1)

Сумма продолжает изменяться таким образом, пока x = p ₂: Наклон равен 1 - (n - 1) = 2 - n После прохождения точки p ₂ наклон изменяется на 2 - (n - 2) = 4 - n, после этого 6 - n, затем 8 - n и т.д.

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

В какой-то момент наклон изменится с отрицательного на

положительный – в случае нечетного числа точек
zero – в случае четного числа точек

Легко видеть, что наклон будет равен нулю в какой-то точке, когда есть четное количество точек:
p ₁ < p ₂ < & Hellip; p _n < p _{n + 1} < & Hellip; p _{2n - 1} < р <суб > 2nсуб >

Если мы находимся между точками p _n и p _{n + 1}, то есть равное количество точек в левой и правой частях. Это означает, что, двигаясь между этими двумя точками, получается равное количество баллов; n, а точнее – приближается и тянет дальше, поэтому сумма S _{p _n <= x <= p _{n + 1}} остается неизменной.

Если существует нечетное число точек, p _{(n + 1)/2} отмечает минимум, потому что это точка, где наклон изменяется с отрицательного на положительный.