LeetCode 296. 最佳的碰头地点

2021-07-24 HGNULB 约 12 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 296. 最佳的碰头地点

题意分析

给一个 m × n 的 0/1 网格，1 表示某个人的家。这些人要在网格的某一格碰头，每个人每次只能上下左右移动一格。求所有人移动的总步数的最小值。

先把「总步数」写成公式。从 $(r_1, c_1)$ 走到 $(r_2, c_2)$ 只能横竖走，最短步数就是曼哈顿距离 $ r_1 - r_2 + c_1 - c_2 $。设人们的家分别在 $(r_i, c_i)$，会合点在 $(R, C)$，那么要最小化的目标是

$f(R, C) = \sum_i ( r_i - R + c_i - C )$。

这个式子里藏着全题的关键：把求和拆开，$f(R, C) = \sum_i r_i - R + \sum_i c_i - C $，前一项只和 $R$ 有关、后一项只和 $C$ 有关，两者完全独立。所以二维的最小化可以拆成两个一维的最小化分别求解，再把结果相加。这是曼哈顿距离特有的性质（欧氏距离就不可分解），也是这道困难题真正的题眼。

拆开之后每个子问题都变成了：在数轴上给定若干点，找一个位置使得到所有点的绝对距离之和最小。这是一个经典结论——答案是这些点的中位数。

还有一处约束值得留意：会合点没有被要求必须是某个人的家，也没有被要求必须落在网格内的空地上，它可以是网格里的任意格子。这一点让我们可以自由取中位数而不必额外校验。反过来，如果题目要求会合点必须避开障碍，中位数就不一定可取，问题会退化成多源 BFS。

边界：至少有一个 1（题目保证），所以中位数一定存在；只有一个人时答案是 0；所有人在同一格时答案也是 0；人数为偶数时中位数不唯一，区间内任意整点都是最优解，取哪个都行。

解法：中位数选点

核心思路

暴力做法是枚举网格里的每一格作为会合点，对每一格再遍历所有人累加距离。设网格有 $mn$ 格、人数为 $p$，总代价是 $O(mn \cdot p)$，最坏情况下 $p$ 与 $mn$ 同阶，达到 $O((mn)^2)$。瓶颈在于：我们把一个有解析解的最优化问题当成了盲目搜索。

第一层观察是上面已经推出的维度可分解：$f(R, C) = g(R) + h(C)$，其中 $g(R) = \sum_i r_i - R $、$h(C) = \sum_i c_i - C $。既然两项互不影响，就可以各自独立取到最小值，$\min f = \min g + \min h$。二维搜索因此降成了两次一维搜索。

第二层观察是一维绝对距离和的最小值点是中位数。这个结论必须能当场证明，否则面试里说不清楚。证明用「移动一步看增量」的方式最直观：设当前位置为 $x$，把它向右挪一格，那么位于 $x$ 左侧（含 $x$）的点到它的距离各增加 1，位于右侧的点各减少 1。设左边有 $L$ 个点、右边有 $R$ 个点，总变化量是 $L - R$。所以只要左边比右边少（$L < R$）就该继续右移，只要左边比右边多就该左移，平衡点正是左右点数相等的位置，也就是中位数。当点数为偶数时，两个中间点之间的整段区间上 $L = R$，增量恒为 0，所以这段区间里任何一点都是最优解，取下中位数或上中位数都对。

于是显式写出算法要维持的量：rows 是所有人的行坐标构成的多重集合，cols 是列坐标构成的多重集合（注意是多重集合，同一行有两个人就要记两次，因为每个人都要独立走路）。取 rows 的中位数作为 $R$、cols 的中位数作为 $C$，答案就是两个一维距离和相加。

实现上有个细节值得说：如果按行优先扫描网格收集坐标，rows 天然就是升序的，不需要排序；只有 cols 需要排序。代码里对两者都排序是为了让逻辑对称、不依赖扫描顺序，代价只是多一次排序，规模上无关紧要。若要追求极致，也可以改成按列优先再扫一遍收集 cols，那样两个数组都天然有序，能把排序完全去掉，总复杂度降到 $O(mn)$。

取中位数写成 list.get(size / 2)：当 size 为奇数时这正是正中间那个；为偶数时取的是上中位数，由前面的证明可知同样最优，不需要写「取两个中位数的平均」——事实上取平均在这里既没必要（会合点必须是整数格）也可能出错。

解题步骤

遍历整个网格，把每个值为 1 的格子的行坐标追加进 rows、列坐标追加进 cols：为什么要拆成两个独立数组——因为最小化问题在两个维度上是独立的，行坐标和列坐标之后再不需要配对；为什么用列表而不是去重的集合——多个人可能同行或同列，每个人都要计一次距离，去重会丢人。

对 rows 和 cols 分别排序：为什么要排序——中位数的定义依赖有序；rows 在行优先扫描下其实已经有序，排序是为了不依赖扫描顺序的健壮写法。

取 rowMid = rows[rows.size() / 2]、colMid = cols[cols.size() / 2]：为什么用整数除法取上中位数——奇数时它就是正中间；偶数时中位数区间内任意整点都最优，取上中位数最省事，不需要分奇偶讨论。

累加 |r - rowMid| 与 |c - colMid|：为什么两部分直接相加就是答案——由 $f(R,C) = g(R) + h(C)$ 的可分解性，两个维度的最优值可以独立取到并相加，不存在「行取最优会牺牲列」的耦合。

返回累加结果：不需要再验证这个点是否真的最优，中位数的最优性已由前面的增量论证保证。

以题目样例 grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] 走一遍，期望答案是 6。

收集坐标：按行优先扫描，(0,0) 是 1，rows 加 0、cols 加 0；(0,4) 是 1，rows 加 0、cols 加 4；第 1 行全 0；(2,2) 是 1，rows 加 2、cols 加 2。得到 rows = [0, 0, 2]、cols = [0, 4, 2]。

排序：rows 已经有序仍是 [0, 0, 2]；cols 排序后变成 [0, 2, 4]。注意 cols 排序前后顺序确实变了，这说明对列排序不是多余动作。

取中位数：rows.size() = 3，3 / 2 = 1，rowMid = rows[1] = 0。cols.size() = 3，colMid = cols[1] = 2。所以会合点是 (0, 2)。

累加行方向距离：|0 - 0| + |0 - 0| + |2 - 0| = 0 + 0 + 2 = 2。
累加列方向距离：|0 - 2| + |2 - 2| + |4 - 2| = 2 + 0 + 2 = 4。
总计 2 + 4 = 6，与期望一致。

手工验证一下这个会合点确实最优：第一个人从 (0,0) 走到 (0,2) 是 2 步，第二个人从 (0,4) 走到 (0,2) 是 2 步，第三个人从 (2,2) 走到 (0,2) 是 2 步，合计 6。若把会合点换成中间那个人的家 (2,2)，则分别是 4、4、0 共 8 步，更差；换成 (1,2) 则是 3、3、1 共 7 步，也更差。中位数点确实最优。

再看一个偶数人数的例子 grid = [[1,1],[1,1]]：rows = [0,0,1,1]、cols = [0,1,0,1] 排序后 [0,0,1,1]。size = 4，4 / 2 = 2，rowMid = rows[2] = 1、colMid = cols[2] = 1。行距离和 1+1+0+0 = 2，列距离和 1+1+0+0 = 2，答案 4。若改取下中位数 rows[1] = 0、cols[1] = 0，行距离和 0+0+1+1 = 2、列距离和同样是 2，答案仍是 4——印证了偶数时两个中位数等价。

最后看单人情形 grid = [[1]]：rows = [0]、cols = [0]，中位数都是 0，距离和为 0，正确。

代码实现

// 一维情况下使绝对距离和最小的是中位数。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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(rows);
        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(rows)
	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(m \cdot n + p \log p)$，其中 $p$ 是人数（$p \le mn$）。凭什么：扫描网格收集坐标要遍历全部 $mn$ 个格子；两次排序各是 $O(p \log p)$；最后两次累加各是 $O(p)$。若利用「行优先扫描下 rows 天然有序、列优先扫描下 cols 天然有序」的性质换成两次扫描收集，可以完全去掉排序，把总复杂度降到 $O(mn)$。

空间复杂度：$O(p)$。凭什么：rows 和 cols 各存 $p$ 个坐标，最坏情况下网格全是 1 时 $p = mn$，所以上界是 $O(mn)$；排序若用快排还有 $O(\log p)$ 的递归栈，不改变量级。这里不能声称 $O(1)$——两个坐标列表是实打实的额外空间。

关键点总结

看到曼哈顿距离就要立刻想到维度可分解：$\sum r_i - R + \sum c_i - C $ 的两项互不影响，二维最优化能拆成两个一维问题独立求解。这是曼哈顿距离区别于欧氏距离的核心性质，也是这类题能有解析解的根本原因。

一维绝对距离和的最小值点是中位数，而绝对距离平方和的最小值点才是平均数。两者极易混淆，务必分清：本题走的是曼哈顿步数，对应绝对值，所以是中位数。

中位数最优性的证明用「向右挪一格，左侧 $L$ 个点各加 1、右侧 $R$ 个点各减 1，净变化 $L - R$」的增量论证最简洁，面试中能现场讲出来比背结论重要得多。它还顺带说明了偶数个点时中位数区间内任意整点都最优。

坐标要按多重集合收集，同一行有几个人就记几次。把「行坐标」误当成「哪些行有人」而去重，是本题最隐蔽的错误。

利用扫描顺序省掉排序（行优先扫出的行坐标天然升序，列优先扫出的列坐标天然升序）是一个值得主动提出的优化，能把 $O(p \log p)$ 降到 $O(p)$。

面试视角：这题的分水岭在于能否独立完成「曼哈顿可分解 → 一维绝对距离和 → 中位数」这条推导链，而不是直接说出答案。回答顺序建议是：先写目标函数，再指出可分解，再证明一维情形取中位数，最后才谈实现和优化。

面试视角：常见追问有两个。其一「为什么不是平均数」，要能举反例——点集 [0, 0, 10] 的平均数是 3.33，距离和是 $3.33+3.33+6.67 \approx 13.3$，而中位数 0 的距离和是 10，中位数更优。其二「如果会合点必须避开障碍物怎么办」，要能答出中位数不再可取，需退化为对每个候选点做多源 BFS 或按人数加权的最短路。

易错点总结

用平均数代替中位数：用例 grid = [[1,0,0,0,0,0,0,0,0,0,1],[0,...],[1,0,...]] 这类分布偏斜的输入，比如一维上的点集 [0, 0, 10]，平均数是 3（整数除法后），距离和为 $3+3+7=13$，而中位数 0 的距离和是 10，答案偏大。

收集坐标时对行去重：用例 grid = [[1,1,1],[0,0,0],[1,0,0]]，第 0 行有 3 个人；若用去重后的 [0,2] 取上中位数 2，再对所有人求行距离，会得到 $2+2+2+0=6$，而正确的多重集合 [0,0,0,2] 取中位数 0，行距离和为 2。

忘记对 cols 排序：用例 grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]，行优先扫描得到 cols = [0,4,2]，不排序直接取 cols[1] = 4 作为会合列，列距离和变成 $4+0+2 = 6$，总答案 8 而正确答案是 6。

误以为 rows 也需要排序而在其他扫描顺序下忘记排序：用例是按列优先扫描收集时 rows 不再有序，若沿用「rows 天然有序」的假设跳过排序，中位数取错。要么两个都排，要么明确各自的扫描顺序，不能想当然。

把两个维度耦合起来枚举「哪个人的家」作为会合点：用例 grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]，最优会合点 (0,2) 根本不是任何人的家，只在人家中枚举会得到 8 而非 6。

对二维直接取「所有 1 坐标的中心」（如包围盒中心）：用例 grid = [[1,1,1,1,0,0,0,0,0,1]] 这种一维偏斜分布，包围盒中心在中点附近，而中位数在左侧密集区，距离和会明显偏大。

误用欧氏距离思路去找几何中位数：用例任意，几何中位数需要迭代求解且不等于按维分解的结果；本题步数是曼哈顿距离，必须按维分解，套欧氏结论会既复杂又错。

空网格或全 0 网格未做防护：用例 grid = [[0,0],[0,0]]，rows 为空，rows.get(0 / 2) 直接越界（Go 版 panic）；题目保证至少有一个人，但写代码时明确这个前提是完整回答的一部分。

声称空间复杂度是 $O(1)$：用例网格全是 1 时 rows 和 cols 各占 $mn$ 个元素，实际是 $O(mn)$；面试中把额外容器的开销漏掉会被直接指出。

累加距离时用 r - rowMid 忘记取绝对值：用例 rows = [0, 0, 2]、rowMid = 0，正负相消后仍得 2 看不出问题；但用例 rows = [0, 2, 4]、rowMid = 2 时会得到 $-2 + 0 + 2 = 0$，而正确的行距离和是 4。

相似题目

题目	难度	考察点
462. 最小操作次数使数组元素相等 II	中等	本题的一维原型，直接考察「绝对距离和最小点是中位数」这一结论
453. 最小操作次数使数组元素相等	中等	操作定义变成「除一个外全部加一」，等价于全部向最小值靠拢，答案换成最小值
215. 数组中的第K个最大元素	中等	求中位数可用快速选择做到 $O(p)$，是本题去掉排序的另一条优化路径
4. 寻找两个正序数组的中位数	困难	中位数的定义在两个有序数组上的推广，考察二分划分而非排序
480. 滑动窗口中位数	困难	动态维护中位数，用对顶堆或有序集合，考察增量更新而非一次性求解
295. 数据流的中位数	困难	流式场景下的中位数维护，重点在两个堆之间的再平衡时机
1200. 最小绝对差	简单	同样靠排序把「任意两元素比较」降成「相邻比较」，练习排序带来的性质