LeetCode刷题-二进制矩阵中的特殊位置

前言说明

算法学习，日常刷题记录。

题目连接

二进制矩阵中的特殊位置

题目内容

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

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

示例1:

输入：

输出：1

解释：(1,2)是一个特殊位置，因为mat[1][2] == 1且所处的行和列上所有其他元素都是0

示例2:

输入：

输出：3

解释：(0,0), (1,1)和(2,2)都是特殊位置

示例3:

输入：

输出：2

示例4:

输入：

输出：3

提示:

rows == mat.length

cols == mat[i].length

1 <= rows, cols <= 100

mat[i][j]是0或1

分析过程

思路：两次矩阵遍历，时间复杂度为O(2nm)，忽略常数项，即为O(nm)，第一次矩阵遍历，找出每个位置的行元素总和、列元素总和；第二次矩阵遍历，找出值为1的位置，判断这个位置是否行元素总和、列元素总和都为1，因为特殊位置规定这个元素对应的行和列的其他元素都为0并且自身为1，所以他们的行元素总和为1，列元素总和也为1。

第一步

定义每个位置的行元素总和，用数组rows表示；定义每个位置的列元素总和，用数组cols表示。

第二步

第一次矩阵遍历，计算这个位置的行元素总和、列元素总和，通过累加来计算。

第三步

再遍历字符串t的字符，每次都把字符和res进行异或运算，结果赋值给res。

第四步

定义矩阵中特殊位置的数目count，第二次矩阵遍历，若这个位置的值为1，并且这个位置的行元素总和为1，列元素总和也为1，那么这个位置就是特殊位置，矩阵中的特殊位置的数目count加1。

第五步

返回矩阵中特殊位置的数目count。

解答代码

class Solution {
    public int numSpecial(int[][] mat) {
        // 两次矩阵遍历，时间复杂度O(nm)，第一次矩阵遍历，找出每个位置的行元素总和、列元素总和；第二次矩阵遍历，找出值为1的位置，判断这个位置是否行元素总和、列元素总和都为1，因为特殊位置规定这个元素对应的行和列的其他元素都为0并且自身为1，所以他们的行元素总和为1，列元素总和也为1

        // 定义每个位置的行元素总和
        int[] rows = new int[mat.length];
        // 定义每个位置的列元素总和
        int[] cols = new int[mat[0].length];

        // 第一次矩阵遍历
        for (int i = 0; i < mat.length; ++i) {
            for (int j = 0; j < mat[i].length; ++j) {
                // 计算这个位置的行元素总和
                rows[i] += mat[i][j];
                // 计算这个位置的列元素总和
                cols[j] += mat[i][j];
            }
        }

        // 定义矩阵中特殊位置的数目
        int count = 0;

        // 第二次矩阵遍历
        for (int i = 0; i < mat.length; ++i) {
            for (int j = 0; j < mat[i].length; ++j) {
                if (mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1) {
                    // 若这个位置的值为1，并且这个位置的行元素总和为1，列元素总和也为1，那么这个位置就是特殊位置，矩阵中的特殊位置的数目加1
                    ++count;
                }
            }
        }

        // 返回矩阵中特殊位置的数目
        return count;
    }
}

提交结果

执行用时2ms，时间击败75.88%的用户，内存消耗38.3MB，空间击败90.27%的用户。

原文链接

原文链接：二进制矩阵中的特殊位置