『LeetCode』1582 二进制矩阵中的特殊位置

题目

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 的数量，即可在 \(O(1)\) 时间内判断矩阵中某个位置是否满足“特殊位置”的要求，随后遍历矩阵统计即可

# Code language: Python
class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        cnt_x = [x.count(1) for x in mat]
        cnt_y = [y.count(1) for y in zip(*mat)]
        
        return sum(y == 1 and cnt_x[i] == 1 and cnt_y[j] == 1 for i, x in enumerate(mat) for j, y in enumerate(x))

// Code language: Java
class Solution {
    public int numSpecial(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[] rows = new int[n], cols = new int[m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (mat[i][j] == 1) {
                    rows[i]++; cols[j]++;
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1) ++cnt;
            }
        }
        return cnt;
    }
}

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

/* Code language: JavaScript */
/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSpecial = function(mat) {
    let n = mat.length, m = mat[0].length;
    const rows = new Array(n).fill(0), cols = new Array(m).fill(0);
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            if (mat[i][j] == 1) {
                rows[i]++; cols[j]++;
            }
        }
    }
    let cnt = 0;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < m; ++j) {
            if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1) ++cnt;
        }
    }
    return cnt;
};

时间复杂度: \(O(n^2)\), 其中 \(n = \max(rows, cols)\)
空间复杂度: \(O(n)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1582 二进制矩阵中的特殊位置

题目

标签

题解

模拟