algorithm - 寻找点，与线上所有其他点的距离总和是最低的

Question

我一直想知道是否有可能以递归或“分而治之”的方式解决这个问题。这是我的问题的可视化：

在此处输入图像描述

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)

我知道如何以迭代的方式做到这一点，但我正在考虑更优化的方法。

score 5 · Accepted Answer

这称为中值。只需对值进行排序并选择中心。如果 n 是偶数，则两个中心值中的任何一个都可以。

还有用于计算中位数的O(n) 算法。

score 2 · Accepted Answer

说解决方案是中位数的答案是正确的，但是可以有

多种解决方案

如果有偶数个点：p ₁ < … p _n < p _{n + 1} < … < p _2n ，对于任何点x ，距离总和将是最小的，其中 *p _n ≤ x ≤ p _{n + 1}

要了解为什么中位数有效，请考虑这个

假设我们有所有适用的p _i < p _i+1n点。i

天真，我们可能认为x = p ₁是最小化总和S的最佳选择。x加一，总和S会发生什么变化？我们离p _{1 更远 1}，但离所有其他点更近 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：接近点的数量减少 1，远离的点数量增加 1，因此坡度变化 2。

在某些时候，斜率将从负变为

很容易看出，当点数为偶数时，斜率会在某个点为零：
p ₁ < p ₂ < … p _n < p _{n + 1} < … p _{2n - 1} < p _2n

如果我们位于点p _n和p _n+1之间，则左侧和右侧的点数量相等。这意味着，当我们在这两个点之间移动时，等量的点 -准确地说是n - 靠近并拉得更远，因此总和S _{p _n <= x <= p _{n + 1}}保持不变。

如果有奇数个点，则p _{(n + 1)/2}标记最小值，因为它是斜率从负变为正的点。