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

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

enter image description here

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 1 < & 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 1 - лучший выбор для минимизации суммы S. Увеличение x на единицу, что происходит с суммой S? Мы находимся дальше от p 1, но 1 ближе ко всем другим точкам.

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

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

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

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

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

Легко видеть, что наклон будет равен нулю в какой-то точке, когда есть четное количество точек:
p 1 < p 2 < & 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 отмечает минимум, потому что это точка, где наклон изменяется с отрицательного на положительный.