背景

最近在社交平台上先后看到两个题，有一定关系，于是在这里做一个总结，大概题意如下：

  1. 给定一个整数数组，找到一个数，使得该数到数组中的每个数的距离之和最小
  2. 在二维平面上给定n个点的坐标，找到一个点，使得该点到这n个点的距离之和最小

事实上第一个问题比较容易解决，数组排序后的中位数即为答案。第二个问题是一个经典的选址问题，下面考虑两种不同的距离：

曼哈顿距离

与一维情况类似，最终点的横纵坐标是所有点的横纵坐标的中位数

欧氏距离

采用weiszfeld算法进行迭代即可，公式如下，

$y_{i+1} = (\sum\limits_{j=1}^{m}\frac{x_j}{||x_j - y_i||})/(\sum\limits_{j=1}^{m}\frac{1}{||x_j - y_i||})$

根据迭代的次数的增加，数据会逐渐的收敛，最后可以计算出最优的候选点，作为最后的位置。

参考：