LeetCode 1582 这道题标题只有一句话统计二进制矩阵里的特殊位置。光看名字很多人会拿它当签到题两分钟写完就过。我第一次刷到它时也是这么干的但后来给团队成员做算法分享时重新读了一遍题才发现这个特殊位置的定义比表面看起来多了一层约束——它不是这一行里唯一的 1就行还要求这一列里也得是唯一的 1。文章就围绕这道题写一份完整的刷题复盘从题意拆解、暴力解法的实际代价到行列和预处理的思路再到边界样例和位掩码扩展把这道简单题里值得抠的细节一次讲清楚。如果你刚开始刷数组、矩阵类题目或者想在二维数组处理上积累通用套路这篇值得读完。1. 特殊位置的精确定义为什么双重唯一才算数1.1 不是这一行里只有一个1就完事先看原题里的判定标准如果一个位置的值是 1并且它所在行的所有其他元素都是 0同时它所在列的所有其他元素也都是 0这个位置才叫特殊位置。注意这里有两个同时行要干净列也要干净。很多人做这道题时的第一反应是我去找每一行里值为 1 的格子如果某行只有一个 1就认为这是一个特殊位置答案加一。这个思路对了一半漏了列方向的校验。我给你一个非常典型的反例1 0 0 0 0 1 1 0 0按只看行的思路第一行只有一个 1在 (0,0)算一个第二行只有一个 1在 (1,2)算一个第三行只有一个 1在 (2,0)又算一个。但正确答案是多少只有 1 个。问题出在列上。位置 (0,0) 和 (2,0) 都在第 0 列这一列有两个 1所以这两个格子都不满足列方向干净的条件。只有 (1,2) 所在的行和列都只有它一个 1才是真正的特殊位置。这个反例基本还原了第一次提交 WA 的全部心路历程。写代码之前不把双重唯一想清楚写出来的判断条件一定是残缺的。1.2 用数学化的方式锁定判定条件为了不让思路含混我习惯先把题干的描述转成可以写进代码的条件。定义一个行向量 rowSum 和一个列向量 colSumrowSum[i] 表示第 i 行中 1 的个数colSum[j] 表示第 j 列中 1 的个数。那么位置 (i, j) 是特殊位置等价于下面三个条件同时成立mat[i][j] 1rowSum[i] 1colSum[j] 1。为什么第二个条件不用写成行内除了当前位置之外所有元素都是 0因为 rowSum[i] 的统计已经把 mat[i][j] 这个 1 算进去了。当 mat[i][j] 1 且 rowSum[i] 1 的时候这一行就不可能再存在另一个 1等价于当前格子是这一行唯一的 1。列方向同理。这里有个容易绕进去的点有人会担心如果当前位置是 0但 rowSum[i] 1那条件二不也成立吗确实成立但没关系因为我们还要求条件一 mat[i][j] 1 必须先满足。当前格子是 1、行里只有一个 1、列里也只有一个 1这三个条件放在一起正好就是题目定义不多不少。把条件写成这样之后解法路径基本就清晰了先统计每行每列的 1 的个数再遍历一次矩阵去核对这三个条件。这套先统计行列信息再二次扫描的模式是二维数组题里出现频率很高的通法。2. 暴力解法先走一遍跑通没问题但代价要看懂2.1 对每个1做行列全扫描的写法最直觉的解法是直接模拟题目定义遍历每个格子遇到 1 就向它所在的行和列做一次完整扫描检查是否存在第二个 1。如果行和列都干净答案加一。def numSpecial_v1(mat): m, n len(mat), len(mat[0]) ans 0 for i in range(m): for j in range(n): if mat[i][j] ! 1: continue ok True # 检查第 j 列的其他位置 for r in range(m): if r ! i and mat[r][j] 1: ok False break # 检查第 i 行的其他位置 if ok: for c in range(n): if c ! j and mat[i][c] 1: ok False break if ok: ans 1 return ans这个版本的逻辑没有任何问题遇到 1 就上下左右检查遇到第二个 1 就提前结束。LeetCode 1582 的矩阵规模不大m、n 的上限我记得是 50所以暴力解法也能通过最多 2500 个格子每个格子扫描不到 100 个位置总操作量在 25 万这个量级完全不会超时。2.2 暴力法暴露的两个问题暴力解法能 AC但我并不建议在面试或者刷题复盘时把它作为最终答案。原因有两个。第一它重复扫描了大量信息。每个 1 都要重新检查自己的行和列而某一行一共有几个 1、某一列一共有几个 1这种信息是固定的可以从一开始就算好没必要每个位置各算一遍。暴力做法相当于每次都重新数一遍同一行同一列信息利用率很低。第二代码分支多容易写出边界错误。上面代码里有两个内层循环每个循环里都要记得排除自身位置r ! i、c ! j。一旦漏掉排除条件当前位置自己就会把自己否决掉结果永远是 0。我在实际帮别人 review 代码时看到过好几次这种错误而且这类错误在样例规模小的时候特别难发现因为样例往往不覆盖同行有多个 1的情况。暴力解法作为第一版思路是可以的但接下来要问自己一个问题能不能通过一次预处理把行、列信息提前算好让第二次遍历时每个位置只用 O(1) 时间判断这就是第三节要说的行列和预处理方案。3. 行列和预处理从 O(mn(mn)) 到 O(mn) 的关键一步3.1 为什么 rowSum[i] 1 和 colSum[j] 1 就足够预处理的核心思路非常简单先算两个数组一个存每行 1 的个数一个存每列 1 的个数然后遍历矩阵。遇到 mat[i][j] 1 时只要 rowSum[i] 1 且 colSum[j] 1就说明这个位置是它所在行和所在列唯一的 1直接计数。这个过程不需要再写两个内层循环去扫描行和列因为 rowSum 和 colSum 已经把某一行/列里有多少个 1这件事浓缩成了两个整数。判断一个位置是否特殊从扫一遍整行整列变成了查两个数单次判断复杂度从 O(mn) 降到了 O(1)。用生活化的例子类比这就像你不需要每次找东西时都把整个房间翻一遍而是提前给每个抽屉贴一张标签写上这里面有什么。第二次进来时直接看标签就够了。标签本身就是一次性的、可复用的统计结果。3.2 标准实现的完整代码一个双循环同时算行和列写代码时有个常见的实现细节我们可以在同一个双层循环里同时累加 rowSum 和 colSum不需要分开两个双层循环。因为遍历到 mat[i][j] 时它既属于第 i 行也属于第 j 列一次访问同时更新两个统计值是顺理成章的。class Solution: def numSpecial(self, mat: List[List[int]]) - int: m, n len(mat), len(mat[0]) row_sum [0] * m col_sum [0] * n for i in range(m): for j in range(n): if mat[i][j] 1: row_sum[i] 1 col_sum[j] 1 ans 0 for i in range(m): for j in range(n): if mat[i][j] 1 and row_sum[i] 1 and col_sum[j] 1: ans 1 return ans如果你在面试现场写 Java逻辑一模一样class Solution { public int numSpecial(int[][] mat) { int m mat.length, n mat[0].length; int[] rowSum new int[m]; int[] colSum new int[n]; for (int i 0; i m; i) { for (int j 0; j n; j) { if (mat[i][j] 1) { rowSum[i]; colSum[j]; } } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (mat[i][j] 1 rowSum[i] 1 colSum[j] 1) { ans; } } } return ans; } }时间复杂度是 O(mn)两个符合并到一起只有两次矩阵遍历空间复杂度 O(mn)用来存行和列统计数组。这个复杂度对于任何矩阵题来说都已经是标准水平。3.3 一个可以继续抠的常数优化先过滤候选行上面第二遍遍历其实还可以做一个小优化我们并不需要遍历所有格子只需要关心那些 rowSum[i] 1 的行这些行中每一行只有唯一一个 1找到它之后再去核对列方向即可。ans 0 for i in range(m): if row_sum[i] ! 1: continue j next(j for j in range(n) if mat[i][j] 1) if col_sum[j] 1: ans 1这版代码更短而且当特殊行很少时可以减少无谓判断。不过要注意前提row_sum[i] 1 时这一行里一定存在且只存在一个值为 1 的格子所以next(...)不会抛异常。这个优化在复杂度量级上没有变化只是换成先过滤行再定位唯一列的思考方式。两种写法本质一样看个人习惯。4. 边界条件与提交复盘从 WA 到 AC 的几处关键细节4.1 单行、单列矩阵的退化场景很多矩阵题在 m 1 或 n 1 的时候容易出问题这题不会因为我们的判定条件天然兼容退化情况。拿 [[1, 0, 0]] 举例只有一行行和 rowSum[0] 1。遍历到 (0,0) 时mat[0][0] 1colSum[0] 1因为第 0 列只有这一个元素所以 (0,0) 是特殊位置。这符合常理一个 1 独占一行一列它当然特殊。再看 [[1, 0, 1]]行和是 2无论哪个 1 都不满足行唯一结果 0也合理。单列的情况同理。这里容易出现的错误直觉是矩阵只有一行或只有一列时列方向是不是就不成立了其实不会一行矩阵里的每个位置仍然属于一个唯一的列列方向只需要看该列是否只有它一个 1而在只有一行的情况下每一列天然只有一个元素所以只要行方向满足且元素本身是 1它一定是特殊位置。4.2 用一组覆盖全面的测试用例自测刷题不能只靠题目自带的样例因为样例往往太温和。我建议提交之前先在本地跑一遍这张表矩阵期望结果判定理由[[1,0,0],[0,1,0],[0,0,1]]3单位矩阵三个对角 1 都同时是行、列唯一[[1,1],[1,1]]0每个 1 所在行列都不唯一[[1,0,1]]0行上有两个 1行不唯一[[1],[0],[1]]0列上有两个 1列不唯一[[1,0,0],[0,1,0]]2两个 1 分别独占所在行和列[[1,0,0],[1,0,0]]0两个 1 在同一列列不唯一这些用例覆盖了行不唯一列不唯一行唯一列唯一全 1 矩阵单行单列几种情况。跑完这张表再去提交心里会踏实很多。4.3 三个最容易踩的坑第一个坑是判断条件的顺序。mat[i][j] 1必须写在最前面或者无论如何不能被丢掉。如果你写成if row_sum[i] 1 and col_sum[j] 1遇到一个值为 0 但恰好所在行、列都只有一个 1 的位置就会错误计数。这个 bug 在矩阵比较稀疏时特别隐蔽输出结果可能差一点点很难一眼看出来。第二个坑是不要在原矩阵上做标记。有人为了省空间想用原地修改的方式记录这一行列过把已经判断过的 1 改成 0。这个想法很危险因为改掉之后会影响后续行的 rowSum、列的 colSum导致统计错乱。老老实实开两个数组时间和空间都完全够用。第三个坑是关于 Python 里zip(*mat)的。有些教程会用col_sum [sum(col) for col in zip(*mat)]来偷懒计算列和这在矩阵规模小的时候不会有问题但面试官如果追问转置的开销你要能说清楚 zip 在 Python 3 里返回的是迭代器*mat展开矩阵会创建新的参数列表矩阵很大时内存并不省。写成显式的双层循环累加逻辑最直白也最不会出错。5. 进阶扩展位掩码写法与矩阵题通用套路5.1 用二进制掩码判断唯一一个1如果只满足于 AC看到第四节就可以结束了。但刷题复盘的价值在于把一个题的做法抽象成可以迁移的思想。这里我再说一个不太常见但很有意思的写法位掩码。由于矩阵里的每个元素都是 0 或 1我们可以把每一行看成一个二进制整数第 j 列是 1 就表示第 j 位是 1。这样某一行只有一个 1等价于这一行对应的二进制整数只有一个 bit 为 1判断方法就是x ! 0 and (x (x - 1)) 0。列方向也做同样的处理只不过每一位对应的是行号。def numSpecial_bit(mat): m, n len(mat), len(mat[0]) row_masks [0] * m col_masks [0] * n for i in range(m): for j in range(n): if mat[i][j] 1: row_masks[i] | 1 j col_masks[j] | 1 i ans 0 for i in range(m): mask row_masks[i] if mask 0 or (mask (mask - 1)) ! 0: continue # 当前行只有一个1找到这一位对应的列 j (mask -mask).bit_length() - 1 col_mask col_masks[j] if col_mask (col_mask - 1) 0: ans 1 return ans这个写法的底层思想仍然是预处理行列信息只是用整数的位运算替代了数组计数。它更适合出现在讨论环节作为一种巧劲展示生产代码里我不会这么写因为可读性差很多。但如果你正在刷位运算专题或者面试官喜欢问有没有更巧的写法主动说出这个思路会加分。5.2 从特殊位置看二维数组题目的通法LeetCode 1582 不算难题但它代表了一类高频题型题目需要反复用到行状态和列状态而这些状态可以在一次遍历中预先算好。比如 LeetCode 73 矩阵置零要求把包含 0 的行和列全部置零。常规思路就是先扫一遍矩阵用两个数组记录哪行哪列有 0第二遍再根据记录原地改写。这和本题先算 rowSum、colSum 再二次扫描的结构几乎一模一样。再比如 LeetCode 2352 相等行列对要统计矩阵中有多少行和列完全相同。做法同样是先收集所有行和所有列的信息再逐一比对。这些题目表面不同骨架都是第一次遍历收集信息第二次遍历利用信息做判断或改写。所以这题真正值得记住的并不是那几行代码而是遇到二维矩阵时先想一步哪些信息是需要被反复查询的能不能在第一个循环里全部算好想清楚这一步很多看起来要嵌套三层循环的题都能压到 O(mn) 级别。我个人做这类矩阵题的习惯是拿到题先问问自己是否真的需要在每个位置上重复扫描整行整列如果不需要就把行列信息提前统计好。这个习惯帮我在不少题上避免了超时也让我写出来的代码一眼就能让别人看懂意图。1582 只是个小例子但预处理这一招后面你会反复用到。