Leetcode 1582. 二进制矩阵中的特殊位置
1.题目描述
给你一个大小为
rows x cols的矩阵mat，其中mat[i][j]是0或1，请返回 矩阵 mat 中特殊位置的数目 。特殊位置 定义：如果
mat[i][j] == 1并且第i行和第j列中的所有其他元素均为0（行和列的下标均 从 0 开始 ），则位置(i, j)被称为特殊位置。
输入：mat = [[1,0,0],
[0,0,1],
[1,0,0]]
输出：1
解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0
输入：mat = [[1,0,0],
[0,1,0],
[0,0,1]]
输出：3
解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
输入：mat = [[0,0,0,1],
[1,0,0,0],
[0,1,1,0],
[0,0,0,0]]
输出：2
输入：mat = [[0,0,0,0,0],
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,1]]
输出：3
提示：
- rows == mat.length
- cols == mat[i].length
- 1 <= rows, cols <= 100
- mat[i][j] 是 0 或 1
2.思路分析
模拟
-
首先需要对矩阵mat进行遍历，来判断哪个位置是“1”，
-
创建两个数组:
- row(用来记录每行存在“1”的个数)
- col(用来记录每列存在“1”的个数)；在这两个数组中，row[index]用来表示第index行有多少个“1”，col[index]用来表示第index列有多少个“1”。
-
确定好只存在1个“1”的行号和列号之后，我们通过判断mat[i][j]是否等于“1”，如果等于，则总数加
1，统计完毕后，将最终结果返回即可。
3.代码实现
class Solution:
def numSpecial(self, mat: List[List[int]]) -> int:
row = [0] * len(mat)
col = [0] * len(mat[0])
result = 0
for i in range(len(mat)):
for j in range(len(mat[0])):
if mat[i][j] == 1:
row[i] += 1
col[j] += 1
for i in range(len(row)):
if row[i] != 1:
continue
for j in range(len(col)):
if col[j] != 1:
continue
if mat[i][j] == 1:
result += 1
return result
复杂度分析:
- 时间复杂度：O(m×n)，其中 m 为矩阵 mat 的行数，n 为矩阵 mat 的列数。
- 空间复杂度：O(m + n)，主要为预处理每一行和列的空间开销。
1.https://leetcode.cn/problems/special-positions-in-a-binary-matrix/solution/zhua-wa-mou-si-by-muse-77-uo39/