最佳的碰头地点
难度:
标签:
题目描述
代码结果
运行时间: 36 ms, 内存: 18.3 MB
/*
* Leetcode 题目：最佳的碰头地点
* 题目思路：
* 1. 给定一个二维的网格，网格中的每一个格子表示一个位置。
* 2. 多个人分别位于不同的格子中，找出一个位置使得这些人到这个位置的总距离最短。
* 3. 使用曼哈顿距离计算：曼哈顿距离是两个点在标准坐标系上的绝对轴距总和。
* 4. 思路是分别找出横坐标和纵坐标的中位数，这样总距离最短。
*/
import java.util.*;
import java.util.stream.*;
public class BestMeetingPointStream {
public int minTotalDistance(int[][] grid) {
List<Integer> rows = IntStream.range(0, grid.length)
.boxed()
.flatMap(i -> IntStream.range(0, grid[0].length)
.filter(j -> grid[i][j] == 1)
.mapToObj(j -> i))
.sorted()
.collect(Collectors.toList());
List<Integer> cols = IntStream.range(0, grid[0].length)
.boxed()
.flatMap(j -> IntStream.range(0, grid.length)
.filter(i -> grid[i][j] == 1)
.mapToObj(i -> j))
.sorted()
.collect(Collectors.toList());
int medianRow = rows.get(rows.size() / 2);
int medianCol = cols.get(cols.size() / 2);
int totalDistance = rows.stream().mapToInt(row -> Math.abs(row - medianRow)).sum()
+ cols.stream().mapToInt(col -> Math.abs(col - medianCol)).sum();
return totalDistance;
}
}
解释
方法:
这个题解的思路是利用中位数的性质来找到最佳的碰头地点。具体步骤如下：
1. 找出所有朋友的家的坐标，并将x坐标和y坐标分别存储在两个列表中。
2. 分别计算x坐标列表和y坐标列表的中位数，作为最佳碰头地点的坐标。
3. 计算所有朋友的家到最佳碰头地点的曼哈顿距离之和，即为最小的总距离。
时间复杂度:
O(mn log(mn))
空间复杂度:
O(mn)
代码细节讲解
🦆
为什么在计算中位数时，如果列表长度是偶数，你选择了返回下中位数而不是平均值？这对最终结果有什么影响？
▷🦆
这个解法中，你提到了使用曼哈顿距离，能否解释为什么曼哈顿距离在这个问题中是适合的而不是欧几里得距离？
▷🦆
在计算中位数时，你对x坐标和y坐标的列表进行了排序。这种排序是否会影响算法的性能，尤其是当朋友的数量非常多时？
▷🦆
在处理边界条件，例如所有朋友的家都位于网格的同一行或同一列时，中位数的计算方法是否还适用？
▷