坐标HW北方某代表处，有外包员工爆料，说搬新家了，两个人一个工位，就给一个凳子。这啥操作？要叠罗汉吗？😂
算法题：通配符匹配
曼哈顿距离在 x 和 y 维度是独立的。也就是说，求横坐标和纵坐标的最优点，可以分开来求。这样我们不用在二维平面上暴力搜索，只需要关注一维的中位数。
数学告诉我们，绝对值和距离最小的点其实就是中位数。对 x 和 y 的坐标排序，分别取中位数作为最佳坐标。 举个简单例子： 假设有 5 个人的 x 坐标是：[1, 2, 9, 12, 15] 中位数是 9。 到 9 的总距离是：|1-9| + |2-9| + |9-9| + |12-9| + |15-9|，最小。
import java.util.*;
public class BestMeetingPoint {
public static int minTotalDistance(int[][] grid) {
List<Integer> rows = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
// 收集所有人的横纵坐标
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) { // 人的位置
rows.add(i);
cols.add(j);
}
}
}
// 排序后找中位数
int rowMedian = findMedian(rows);
int colMedian = findMedian(cols);
// 计算总距离
return calculateDistance(rows, rowMedian) + calculateDistance(cols, colMedian);
}
private static int findMedian(List<Integer> points) {
Collections.sort(points);
return points.get(points.size() / 2); // 中位数
}
private static int calculateDistance(List<Integer> points, int median) {
int distance = 0;
for (int point : points) {
distance += Math.abs(point - median);
}
return distance;
}
public static void main(String[] args) {
int[][] grid = {
{1, 0, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 0, 1, 0, 0}
};
System.out.println(minTotalDistance(grid)); // 输出：6
}
}
坐标收集：我们先把所有有人的点横纵坐标分开存入两个列表。 中位数求解：将横纵坐标排序后取中位数，分维度求解。 距离计算：用绝对值的方式算所有点到中位数的距离，最后相加。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
