二进制矩阵中的特殊位置
难度:
标签:
题目描述
给定一个 m x n
的二进制矩阵 mat
,返回矩阵 mat
中特殊位置的数量。
如果位置 (i, j)
满足 mat[i][j] == 1
并且行 i
与列 j
中的所有其他元素都是 0
(行和列的下标从 0 开始计数),那么它被称为 特殊 位置。
示例 1:

输入:mat = [[1,0,0],[0,0,1],[1,0,0]] 输出:1 解释:位置 (1, 2) 是一个特殊位置,因为 mat[1][2] == 1 且第 1 行和第 2 列的其他所有元素都是 0。
示例 2:

输入:mat = [[1,0,0],[0,1,0],[0,0,1]] 输出:3 解释:位置 (0, 0),(1, 1) 和 (2, 2) 都是特殊位置。
提示:
m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j]
是0
或1
。
代码结果
运行时间: 31 ms, 内存: 16.5 MB
/*
* 思路:
* 使用Java Stream API来简化代码。
* 对于每个元素为1的位置,使用Stream API检查其所在行和列的其他所有元素是否都为0。
*/
import java.util.stream.IntStream;
public class Solution {
public int numSpecial(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
return (int) IntStream.range(0, m).boxed()
.flatMap(i -> IntStream.range(0, n).filter(j -> mat[i][j] == 1).mapToObj(j -> new int[]{i, j}))
.filter(pos -> isSpecial(mat, pos[0], pos[1]))
.count();
}
private boolean isSpecial(int[][] mat, int row, int col) {
return IntStream.range(0, mat[0].length).allMatch(j -> j == col || mat[row][j] == 0) &&
IntStream.range(0, mat.length).allMatch(i -> i == row || mat[i][col] == 0);
}
}
解释
方法:
此题解的核心思想是首先遍历每一行,判断行内元素之和是否大于1。如果大于1,则该行不可能含有特殊位置,直接跳过。如果不大于1(即只有一个1或全0),则进一步检查每个为1的元素。对于每一个1,检查其所在列的其他行是否也为1。如果当前列其他行有1,则当前位置不是特殊位置。这个过程中,通过维护一个结果计数器res来记录特殊位置的数量。
时间复杂度:
O(m^2 * n)
空间复杂度:
O(1)
代码细节讲解
🦆
在遍历每行时,你是如何确保即使行元素之和为1时,该元素的列中没有其他的1?
▷🦆
如果一个行内只有一个1,但其对应列中的其他行也有1,这种情况下题解中的逻辑是否仍然有效?
▷🦆
题解中提到,如果行内元素之和大于1则直接跳过,这是否意味着全0行也会被跳过?全0行是否应该被考虑?
▷🦆
对于内层循环,为什么选择遍历每一列而不是只在发现行的和为1时,直接找到该1的位置并检查其列?
▷