寻找点,与线上所有其他点的距离总和最小

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)

我知道如何以迭代的方式做到这一点,但我正在考虑更优化的事情.

Answer 1

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

还有用于计算中值的O(n)算法.

概要证明是，如果你左边有N个点，并且>=N+2个点在你右边，那么你所在的位置并不是问题的解，因为向右移动一个点你将距离> = N + 2点减少一些常数d，然后将距离增加到N + 1点相同的常数d（N + 1是左边的N点，加上你所在的点）。这减少了总数。因此，除非您在一侧有 (a) N 个点，或 (b) 一侧有 N 个点，另一侧有 N+1 个点，否则您就无法找到解决方案。因此解就是中位数。 (2认同)