侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-04 / 0 评论 / 0 点赞 / 38 阅读 / 798 字 / 正在检测是否收录...

题目

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


给你一个大小为 rows x cols 的矩阵 mat,其中 mat[i][j]01,请返回 矩阵 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]01

解题

方法一:暴力 模拟

思路

直接按照题目模拟:枚举矩阵中每个位置,如果该位置值为 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;
    }
};
0

评论区