LeetCode 1515: Best Position for a Service Centre
Problem Description
Explanation:
To solve this problem, we can use gradient descent optimization. We will start with an initial guess for the center position and iteratively update it to minimize the sum of distances to all customers. At each iteration, we will calculate the partial derivatives of the total distance with respect to the x and y coordinates of the center and adjust the center position accordingly.
- Initialize the center position randomly.
- Iterate until convergence:
- Calculate the gradient of the total distance with respect to x and y.
- Update the center position based on the gradient and a learning rate.
- Repeat the above steps until the center position converges.
Time Complexity: O(n) where n is the number of customers
Space Complexity: O(1)
:
Solutions
class Solution {
public double getMinDistSum(int[][] positions) {
double learningRate = 1e-7;
double eps = 1e-8;
double[] center = {50, 50}; // Initial guess for center position
while (true) {
double[] gradient = {0, 0};
double totalDist = 0;
double denominator = 0;
for (int[] pos : positions) {
double dist = Math.sqrt(Math.pow(center[0] - pos[0], 2) + Math.pow(center[1] - pos[1], 2));
gradient[0] += (center[0] - pos[0]) / dist;
gradient[1] += (center[1] - pos[1]) / dist;
totalDist += dist;
denominator += 1 / dist;
}
if (Math.max(Math.abs(gradient[0]), Math.abs(gradient[1])) < eps) {
break;
}
center[0] -= learningRate * gradient[0] / denominator;
center[1] -= learningRate * gradient[1] / denominator;
}
return totalDist;
}
}Loading editor...