题目描述

给你一个大小为 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

算法分析

模拟

• 枚举二维数组中的每个位置，若当前位置是1，且除了该位置，当前行和当前列的其他元素都是0，则表示该位置满足要求

时间复杂度 $O(n^3)$

Java 代码

class Solution {
    public int numSpecial(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int res = 0;
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < m;j ++)
            {

                if(mat[i][j] == 1)
                {
                    boolean flag = true;
                    for(int k = 0;k < n;k ++) if(k != i && mat[k][j] == 1) flag = false;
                    for(int k = 0;k < m;k ++) if(k != j && mat[i][k] == 1) flag = false;
                    if(flag) res ++;
                }
            }
        return res;
    }
}