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

题目描述：

给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。

特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。

题目解析：

一开始是这样想的，我想通过预处理看能不能实现O（N）的时间复杂度，然后发现不可行，然后实现了O（N*M）的时间复杂度和O（N+M）的空间复杂度。

先用暴力解法，遍历二维矩阵中的所有点，然后根据特殊位置进行判断，如果该点值为1并且在所在行列内没有其他为1的点，说明该值为特殊点，最后返回统计的特殊点的个数，代码如下：

class Solution {
    public int numSpecial(int[][] mat) {
        int ans = 0;
        for(int i = 0; i<mat.length ; i++){
            for(int j = 0 ; j<mat[0].length ; j++){
                if(mat[i][j]==1){
                    if(cal(mat,i,j))ans++;
                }
            }
        }
        return ans;
    }

    boolean cal(int[][] mat, int row , int col){
        int sum = 0;
        for(int i = 0; i<mat.length ; i++){
            if(mat[i][col]==1)sum++;
        }
        for(int i = 0; i<mat[0].length ; i++){
            if(mat[row][i]==1)sum++;
        }
        if(sum==2)return true;
        return false;
    }
}

时间复杂度为O(N*M*(N+M)), 空间复杂度为O(1)。

执行用时：5 ms, 在所有 Java 提交中击败了6.90%的用户

内存消耗：41.5 MB, 在所有 Java 提交中击败了66.81%的用户

使用两个矩阵作为行列的标记为，来标记该行该列有多少个1值，若某行只有一个1，某列也只有一个1，并且该行该列的交点于矩阵中也为1，则该点为一个特殊点。代码如下：

// java
class Solution {
    public int numSpecial(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        int ans = 0;
        int[] flag_row = new int[row];
        int[] flag_col = new int[col];
        for(int i = 0; i<row ; i++){
            for(int j = 0; j<col ; j++){
                if(mat[i][j]==1){
                    flag_row[i]++;
                    flag_col[j]++;
                }
            }
        }
        for(int i = 0; i<row ; i++){
            for(int j = 0 ; j<col ; j++){
                if(flag_row[i]==1&&flag_col[j]==1&&mat[i][j]==1)ans++;
            }
        }
        return ans;
    }
}

时间复杂度为O(N*M), 空间复杂度为O(N+M)。

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：41.4 MB, 在所有 Java 提交中击败了77.59%的用户

// cpp
class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int ans(0);
        int row = mat.size();
        int col = mat[0].size();
        vector<int> f_r(row,0);
        vector<int> f_c(col,0);
        for(int i = 0 ; i<row ; i++){
            for(int j = 0 ; j<col ; j++){
                f_r[i] += mat[i][j];
                f_c[j] += mat[i][j];
            }
        }
        for(int i = 0 ; i<row ; i++){
            for(int j = 0 ; j<col ; j++){
                if(f_r[i]==1&&f_c[j]==1&&mat[i][j]==1)ans++;
            }
        }
        return ans;
    }
};

执行用时：20 ms, 在所有 C++ 提交中击败了49.00%的用户

内存消耗：12.6 MB, 在所有 C++ 提交中击败了46.59%的用户