【暴力, 模拟, 矩阵】二进制矩阵中的特殊位置

题目

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

---

给你一个大小为 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.length
• cols == mat[i].length
• 1 <= rows, cols <= 100
• mat[i][j] 是 0 或 1

解题

方法一：暴力 模拟

思路

直接按照题目模拟：枚举矩阵中每个位置，如果该位置值为 1 就循环找该行、该列有没有更多的 1，如果没有，该位置就是特殊位置，计数(cnt)增加。

代码

class Solution {
    public int numSpecial(int[][] mat) {
        int rows = mat.length, cols = mat[0].length;
        int cnt = 0;
        for (int i = 0; i < rows; ++i) {
            outer: for (int j = 0; j < cols; ++j) {
                if (mat[i][j] == 0) continue;
                for (int k = 0; k < rows; ++k) {
                    if (k == i) continue;
                    if (mat[k][j] == 1) continue outer;
                }
                for (int k = 0; k < cols; ++k) {
                    if (k == j) continue;
                    if (mat[i][k] == 1) continue outer;
                }
                ++cnt;
            }
        }
        return cnt;
    }
}

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int rows = mat.size(), cols = mat[0].size();
        int cnt = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (!mat[i][j]) continue;
                for (int k = 0; k < rows; ++k) {
                    if (k == i) continue;
                    if (mat[k][j]) goto out;
                }
                for (int k = 0; k < cols; ++k) {
                    if (k == j) continue;
                    if (mat[i][k]) goto out;
                }
                ++cnt;
                out:;
            }
        }
        return cnt;
    }
};

方法二：暴力 预处理

思路

预处理统计每行、每列 1 的个数，如果发现 mat[i][j] == 1 且第 i 行只有一个 1，第 j 列只有一个1，就说明这是一个特殊位置，计数(cnt)增加。

代码

class Solution {
    public int numSpecial(int[][] mat) {
        int rows = mat.length, cols = mat[0].length;
        int[] rowSums = new int[rows], colSums = new int[cols];
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (mat[i][j] == 1) {
                    ++rowSums[i];
                    ++colSums[j];
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (mat[i][j] == 1 && rowSums[i] == 1 && colSums[j] == 1)
                    ++cnt;
            }
        }
        return cnt;
    }
}

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int rows = mat.size(), cols = mat[0].size();
        vector<int> row_sums(rows), col_sums(cols);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (mat[i][j]) ++row_sums[i], ++col_sums[j];
            }
        }
        int cnt = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (mat[i][j] && row_sums[i] == 1 && col_sums[j] == 1)
                    ++cnt;
            }
        }
        return cnt;
    }
};