LeetCode 题解工作台
服务中心的最佳位置
一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。 给你一个数组 positions ，其中 positions[i] = [x i , y i ] 表示第 i 个客户在二维…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
我们可以先设定一个初始的服务中心位置为所有客户坐标的几何中心 $(x, y)$。接下来，使用梯度下降法不断迭代，设定一个学习率 ，衰减率 。每次一次迭代，计算当前位置到所有客户的距离之和，然后计算当前位置的梯度，最后更新当前位置。当梯度的绝对值都小于 时，停止迭代，返回当前位置到所有客户的距离之和。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。
给你一个数组 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 <= 50positions[i].length == 20 <= xi, yi <= 100
解题思路
方法一：梯度下降法
我们可以先设定一个初始的服务中心位置为所有客户坐标的几何中心 。接下来，使用梯度下降法不断迭代，设定一个学习率 ，衰减率 。每次一次迭代，计算当前位置到所有客户的距离之和，然后计算当前位置的梯度，最后更新当前位置。当梯度的绝对值都小于 时，停止迭代，返回当前位置到所有客户的距离之和。
class Solution:
def getMinDistSum(self, positions: List[List[int]]) -> float:
n = len(positions)
x = y = 0
for x1, y1 in positions:
x += x1
y += y1
x, y = x / n, y / n
decay = 0.999
eps = 1e-6
alpha = 0.5
while 1:
grad_x = grad_y = 0
dist = 0
for x1, y1 in positions:
a = x - x1
b = y - y1
c = sqrt(a * a + b * b)
grad_x += a / (c + 1e-8)
grad_y += b / (c + 1e-8)
dist += c
dx = grad_x * alpha
dy = grad_y * alpha
x -= dx
y -= dy
alpha *= decay
if abs(dx) <= eps and abs(dy) <= eps:
return dist
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate suggests optimization techniques such as gradient descent or geometric median algorithms.
- question_mark
Assess whether the candidate acknowledges the trade-off between brute force and optimized solutions based on input size.
- question_mark
Observe if the candidate can discuss convergence criteria for iterative algorithms like geometric median methods.
常见陷阱
外企场景- error
Candidates may overlook the need for optimization methods and suggest brute force approaches that are inefficient for larger inputs.
- error
The challenge of convergence in geometric median algorithms might be missed, leading to inefficient or incorrect solutions.
- error
Failing to handle edge cases such as minimal input size (e.g., only one customer) could lead to incorrect solutions.
进阶变体
外企场景- arrow_right_alt
Expand the problem to include obstacles or blocked areas that the service center cannot be built upon.
- arrow_right_alt
Introduce multiple service centers and ask for the optimal placement for all, minimizing distances for multiple centers.
- arrow_right_alt
Modify the problem to account for weighted distances, where some customers have higher priority than others.