Hard

题目描述

一家快递公司希望在一个新城市建立新的服务中心。该公司知道这个城市中所有客户在 2D 地图上的位置，并希望在一个能使到所有客户的欧几里得距离之和最小的位置建立新的中心。

给定一个数组 positions，其中 positions[i] = [xi, yi] 是第 i 个客户在地图上的位置，请返回到所有客户的欧几里得距离之和的最小值。

换句话说，你需要选择服务中心的位置 [xcentre, ycentre]，使得下面的公式最小化：

与实际值相差 10^-5 以内的答案将被接受。

示例 1：

输入：positions = [[0,1],[1,0],[1,2],[2,1]]
输出：4.00000
解释：如图所示，选择 [xcentre, ycentre] = [1, 1] 会使到每个客户的距离都等于 1，所有距离之和为 4，这是我们能达到的最小值。

示例 2：

输入：positions = [[1,1],[3,3]]
输出：2.82843
解释：最小可能的距离和 = sqrt(2) + sqrt(2) = 2.82843

约束：

  • 1 <= positions.length <= 50
  • positions[i].length == 2
  • 0 <= xi, yi <= 100

解题思路

这是一个经典的几何中位数问题，目标是找到一个点，使得到所有给定点的欧几里得距离之和最小。

核心思路： 这个问题在数学上被称为费马点（Fermat Point）或几何中位数问题。对于欧几里得距离，目标函数不是凸函数，但可以使用梯度下降等优化算法求解。

解法分析：

  1. 梯度下降法：从一个初始点开始，计算梯度方向，朝着使目标函数减小的方向移动
  2. 三元搜索：在x和y两个维度上分别进行三元搜索
  3. 模拟退火：使用随机化方法避免局部最优

推荐解法：梯度下降

  • 初始点选择所有点的重心（平均坐标）
  • 计算当前点到所有目标点的梯度
  • 沿着负梯度方向移动，逐步缩小步长
  • 当步长足够小时停止迭代

对于点(x,y)，到点(xi,yi)的距离的梯度为：

  • ∂f/∂x = (x-xi)/sqrt((x-xi)² + (y-yi)²)
  • ∂f/∂y = (y-yi)/sqrt((x-xi)² + (y-yi)²)

特别注意当距离为0时需要特殊处理，避免除零错误。

代码实现

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        double x = 0, y = 0;
        int n = positions.size();
        
        // 初始化为重心
        for (auto& pos : positions) {
            x += pos[0];
            y += pos[1];
        }
        x /= n;
        y /= n;
        
        double step = 100;
        double eps = 1e-7;
        
        while (step > eps) {
            double dx = 0, dy = 0;
            
            // 计算梯度
            for (auto& pos : positions) {
                double diffX = x - pos[0];
                double diffY = y - pos[1];
                double dist = sqrt(diffX * diffX + diffY * diffY);
                
                if (dist > eps) {
                    dx += diffX / dist;
                    dy += diffY / dist;
                }
            }
            
            // 更新位置
            x -= step * dx;
            y -= step * dy;
            step *= 0.999;
        }
        
        // 计算最终距离和
        double result = 0;
        for (auto& pos : positions) {
            double diffX = x - pos[0];
            double diffY = y - pos[1];
            result += sqrt(diffX * diffX + diffY * diffY);
        }
        
        return result;
    }
};

class Solution:
    def getMinDistSum(self, positions: List[List[int]]) -> float:
        x = sum(pos[0] for pos in positions) / len(positions)
        y = sum(pos[1] for pos in positions) / len(positions)
        
        step = 100
        eps = 1e-7
        
        while step > eps:
            dx = dy = 0
            
            # 计算梯度
            for px, py in positions:
                diff_x = x - px
                diff_y = y - py
                dist = (diff_x * diff_x + diff_y * diff_y) ** 0.5
                
                if dist > eps:
                    dx += diff_x / dist
                    dy += diff_y / dist
            
            # 更新位置
            x -= step * dx
            y -= step * dy
            step *= 0.999
        
        # 计算最终距离和
        result = 0
        for px, py in positions:
            result += ((x - px) ** 2 + (y - py) ** 2) ** 0.5
        
        return result

public class Solution {
    public double GetMinDistSum(int[][] positions) {
        double x = 0, y = 0;
        int n = positions.Length;
        
        // 初始化为重心
        for (int i = 0; i < n; i++) {
            x += positions[i][0];
            y += positions[i][1];
        }
        x /= n;
        y /= n;
        
        double step = 100;
        double eps = 1e-7;
        
        while (step > eps) {
            double dx = 0, dy = 0;
            
            // 计算梯度
            for (int i = 0; i < n; i++) {
                double diffX = x - positions[i][0];
                double diffY = y - positions[i][1];
                double dist = Math.Sqrt(diffX * diffX + diffY * diffY);
                
                if (dist > eps) {
                    dx += diffX / dist;
                    dy += diffY / dist;
                }
            }
            
            // 更新位置
            x -= step * dx;
            y -= step * dy;
            step *= 0.999;
        }
        
        // 计算最终距离和
        double result = 0;
        for (int i = 0; i < n; i++) {
            double diffX = x - positions[i][0];
            double diffY = y - positions[i][1];
            result += Math.Sqrt(diffX * diffX + diffY * diffY);
        }
        
        return result;
    }
}

var getMinDistSum = function(positions) {
    let x = positions.reduce((sum, pos) => sum + pos[0], 0) / positions.length;
    let y = positions.reduce((sum, pos) => sum + pos[1], 0) / positions.length;
    
    let step = 100;
    const eps = 1e-7;
    
    while (step > eps) {
        let dx = 0, dy = 0;
        
        // 计算梯度
        for (let [px, py] of positions) {
            const diffX = x - px;
            const diffY = y - py;
            const dist = Math.sqrt(diffX * diffX + diffY * diffY);
            
            if (dist > eps) {
                dx += diffX / dist;
                dy += diffY / dist;
            }
        }
        
        // 更新位置
        x -= step * dx;
        y -= step * dy;
        step *= 0.999;
    }
    
    // 计算最终距离和
    let result = 0;
    for (let [px, py] of positions) {
        result += Math.sqrt((x - px) * (x - px) + (y - py) * (y - py));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × k)，其中 n 是点的数量，k 是迭代次数（通常为常数）
空间复杂度O(1)，只使用了常数额外空间