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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析:

• 时间复杂度：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/