【1582. 二进制矩阵中的特殊位置】

来源：力扣（LeetCode）

描述：

给你一个大小为 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
1
2
3
4
5

示例 2：

输入：mat = [[1,0,0],
            [0,1,0],
            [0,0,1]]
输出：3
解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
1
2
3
4
5

示例 3：

输入：mat = [[0,0,0,1],
            [1,0,0,0],
            [0,1,1,0],
            [0,0,0,0]]
输出：2
1
2
3
4
5

示例 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
1
2
3
4
5
6

提示：

• rows == mat.length
• cols == mat[i].length
• 1 <= rows, cols <= 100
• mat[i][j] 是 0 或 1

方法一：模拟

思路与算法

题目给定了一个大小为 m × n 的矩阵 mat，并满足矩阵中的任意元素为 1 或者 0。现在给出特殊位置的定义：如果 mat[i][j] = 1, i ∈ [0,m), j ∈ [0,n)，并且第 i 行和第 j 列的其他元素均为 0，则位置 (i, j) 为特殊位置。那么我们枚举每一个位置，然后按照特殊位置的定义来判断该位置是否满足要求，又因为矩阵中的每一个元素只能为 1 或者 0，所以我们可以预处理出每一行和列的和来快速的得到每一行和列中的 1 的个数。

代码：

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> rowsSum(m);
        vector<int> colsSum(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowsSum[i] += mat[i][j];
                colsSum[j] += mat[i][j];
            }
        }
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1 && rowsSum[i] == 1 && colsSum[j] == 1) {
                    res++;
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

执行用时：16 ms, 在所有 C++ 提交中击败了82.73%的用户
内存消耗：12.5 MB,在所有 C++ 提交中击败了57.83%的用户
复杂度分析
时间复杂度： 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 行，那么标记值也是第 i 行中的 1 的数量，即：第 i 行也有且仅有这个 1。所以 (i, j) 为特殊位置。

那么整个矩阵的特殊位置的数量就是最后标记值为 1 的列的数量。

进一步地，我们可以用原始矩阵的第一行来作为我们标记列的额外空间，从而使空间复杂度降至 O(1)。

代码：

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        for (int i = 0; i < m; i++) {
            int cnt1 = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    cnt1++;
                }
            }
            if (i == 0) {
                cnt1--;
            }
            if (cnt1 > 0) {
                for (int j = 0; j < n; j++) {
                    if (mat[i][j] == 1) {
                        mat[0][j] += cnt1;
                    }
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mat[0][i] == 1) {
                sum++;
            }
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

执行用时：12 ms, 在所有 C++ 提交中击败了97.19%的用户
内存消耗：12.5 MB, 在所有 C++ 提交中击败了69.48%的用户
复杂度分析
时间复杂度： O(m×n)，其中 m 为矩阵 mat 的行数，n 为矩阵 mat 的列数。
空间复杂度： O(1)，由于用了原始矩阵的空间来作为我们的辅助空间，所以我们仅使用常量空间。
author：LeetCode-Solution