【2022-09-04每日一题】1582. 二进制矩阵中的特殊位置
2022-09-04
3分钟阅读时长
2022-09-04每日一题：1582. 二进制矩阵中的特殊位置
- 难度：Easy
- 标签：数组 、 矩阵
给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。
特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。
示例 1：
输入：mat = [[1,0,0], [0,0,1], [1,0,0]] 输出：1 解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0
示例 2：
输入：mat = [[1,0,0], [0,1,0], [0,0,1]] 输出：3 解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
示例 3：
输入：mat = [[0,0,0,1], [1,0,0,0], [0,1,1,0], [0,0,0,0]] 输出：2
示例 4：
输入：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.lengthcols == mat[i].length1 <= rows, cols <= 100mat[i][j]是0或1
方法一：模拟
func numSpecial(mat [][]int) (ans int) {
rowsSum, colsSum := make([]int, len(mat)), make([]int, len(mat[0]))
for i, rows := range mat {
for j, num := range rows {
// 计算每行每列有多少个1
rowsSum[i]+=num
colsSum[j]+=num
}
}
for i, rows := range mat {
for j, num := range rows {
if num == 1 && rowsSum[i] == 1 && colsSum[j] == 1 {
ans++
}
}
}
return ans
}
复杂度分析
- 时间复杂度：O(m×n)，其中 m 为矩阵 mat 的行数，n 为矩阵 mat 的列数。
- 空间复杂度：O(m+n)，主要为预处理每一行和列的空间开销。
方法二：列的标记值
思路
在方法一的基础上，我们可以看到对于 (i,j)，它为特殊位置的条件为mat[i][j]=1 且该行和该列中 1 的数量都为 1。据此，定义第 j 列的标记值为：该列所有 1 所在行中的 1 的数量之和。下面证明，(i,j) 为特殊位置的充要条件是，第 j列的标记值恰好为 1：
如果 (i,j) 为特殊位置，则说明第 j 列只有一个 1，这一个 1 所在的第 i 行也只有它这一个 1，那么按照标记值的定义可得，第 j列的标记值为1。 如果第 j 列的标记值为 1，那么说明该列只能有一个 1。反证：如果有 x 个 1（x > 1），则第 j 列的标记值一定 ≥x。既然只能有一个 1，设其在第 行，那么标记值也是第 i 行中的 1 的数量，即：第 i 行也有且仅有这个 1。所以 (i,j) 为特殊位置。 那么整个矩阵的特殊位置的数量就是最后标记值为 1 的列的数量。
进一步地，我们可以用原始矩阵的第一行来作为我们标记列的额外空间，从而使空间复杂度降至 O(1)。
代码
// 压缩
func numSpecial(mat [][]int) (ans int) {
for i, row := range mat {
cnt1 := 0
// 遍历列，统计第i行中的1的个数
for _, x := range row {
cnt1 += x
}
// 记录代表的行
if i == 0 {
// 若代表行正好有元素1
// 直接累计cnt则会出现重复计算的bug
cnt1--
}
// 其实可以不判，因为该行没有1，永远不会累计上-1
if cnt1 > 0 {
// 遍历列，若该列有1，则代表col中累计这行的1的个数
for j, x := range row {
if x == 1 {
mat[0][j] += cnt1
}
}
}
}
for _, x := range mat[0] {
if x == 1 {
ans++
}
}
return ans
}
cpp
// 非压缩
class Solution {
public:
int numSpecial(vector<vector<int>>& mat) {
int n = mat.size();
int m = mat[0].size();
// 每列中数字是1的那行
// 的1的个数之和
// 最后只有col[i] == 1才是合格的
vector<int> col(m);
for (int i = 0; i < n; i += 1) {
int cnt = 0;
// 遍历列
// 统计第i行中的1的个数
for (int j = 0; j < m; j += 1) {
cnt += mat[i][j];
}
// 遍历列
// 若该列有1，则代表col中累计这行的1的个数
for (int j = 0; j < m; j += 1) {
if (mat[i][j] == 1) {
col[j] += cnt;
}
}
}
return count(col.begin(), col.end(), 1);
}
};
复杂度分析
- 时间复杂度：O(m×n)，其中 m 为矩阵 mat 的行数，n 为矩阵 mat 的列数。
- 空间复杂度：O(1) 。