LeetCode 296. 最佳的碰头地点
题目描述
题意分析
网格中每个值为 $1$ 的格子代表一个人。选择一个会合格子，使所有人走到这里的曼哈顿距离之和最小；两点之间的距离是行坐标差的绝对值加列坐标差的绝对值。会合点不必是某个人原来的位置。
解法：行列中位数
核心思路
[!blue]
设会合点为 (R, C)。把每个人的曼哈顿距离展开再求和，可以写成 $\sumrow-R + \sum col-C $。第一部分只受 R影响，第二部分只受C影响，因此可以分别找出行、列方向的最优坐标，再把它们组合成一个会合点。
对一维坐标排序后，为什么中位数最优？把最小坐标 x与最大坐标y配成一对。对任意会合位置t，都有 $x-t + y-t \ge y-x$；当 t位于[x, y]内时，两段距离恰好组成y-x，达到这一对能取到的最小值。再把第二小与第二大配对，依次向中间收缩。这些配对区间相互嵌套，中位数位于每个区间中，可以同时让所有配对达到各自的下界。人数为奇数时，剩下的中间一人到中位数的距离为 $0$；人数为偶数时，两个中间坐标之间的任意位置都最优，代码取下标
人数 / 2对应的较大中位数即可。扫描网格时，每遇到一个人就分别记录它的行、列坐标。同行或同列的人仍然各贡献一次距离，不能去重。当前代码按行从小到大扫描，所以
rows已经有序；列坐标在每一行都会重新从左开始，cols未必整体有序，需要单独排序。最后分别选出两个中位数，并对所有行坐标、列坐标累加绝对差。独立选择坐标只影响距离计算，不需要保留某个行坐标与原列坐标的配对关系。
解题步骤
- 按行扫描，收集每个人的行列坐标。
- 行坐标已按序收集，只将列坐标排序。
- 分别取中位数，累加两个方向的绝对距离。
代码实现
class Solution {
public int minTotalDistance(int[][] grid) {
List<Integer> rows = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
int m = grid.length;
int n = grid[0].length;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1) {
rows.add(r);
cols.add(c);
}
}
}
// 按行扫描已使行坐标有序，只需将列坐标排序。
Collections.sort(cols);
// 行列独立取中位数，重复坐标按人数保留。
int rowMid = rows.get(rows.size() / 2);
int colMid = cols.get(cols.size() / 2);
int answer = 0;
for (int r : rows) {
answer += Math.abs(r - rowMid);
}
for (int c : cols) {
answer += Math.abs(c - colMid);
}
return answer;
}
}
import "sort"
func minTotalDistance(grid [][]int) int {
rows := make([]int, 0)
cols := make([]int, 0)
m := len(grid)
n := len(grid[0])
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if grid[r][c] == 1 {
rows = append(rows, r)
cols = append(cols, c)
}
}
}
// 按行扫描已使行坐标有序，只需将列坐标排序。
sort.Ints(cols)
// 行列独立取中位数，重复坐标按人数保留。
rowMid := rows[len(rows)/2]
colMid := cols[len(cols)/2]
answer := 0
for _, r := range rows {
if r >= rowMid {
answer += r - rowMid
} else {
answer += rowMid - r
}
}
for _, c := range cols {
if c >= colMid {
answer += c - colMid
} else {
answer += colMid - c
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(mn+p\log(p+1))$，p 为人数，包含网格扫描、坐标排序与累加。
- 空间复杂度：$O(p)$，保存两组坐标。
关键点总结
[!green]
- 绝对距离和由中位数最小化，不是由平均数。
- 会合点不必是某个人的家。
- 重复坐标代表不同人的贡献，需要保留次数。
易错点总结
[!yellow]
- 对同行或同列坐标去重：改变了各位置的人数权重。
- 未排序就取中间项：中间下标不一定代表中位数。
- 只在人们的家中选择会合点：可能排除真正的最优格子。
- 距离直接相减不取绝对值：两侧距离会相互抵消。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 462. 最小操作次数使数组元素相等 II | 中等 | 曼哈顿距离可拆成横纵两轴的一维绝对距离和，每一轴都由中位数最小化。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！