LEETCODE 1582. Special Positions in a Binary Matrix 解题思路分析

题目大意：

二进制矩阵中的特殊位置

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

---

前言：

最近很多朋友私信我，问到为什么最近博客更新变少了？这里统一回复一下，真的非常抱歉，最近接了一个私活，项目很大，而且是从零开始的那种。从项目架构到云服务器搭建，以及数据库设计，api设计，web端，app端甚至各种小程序端都有所涉及。事无巨细，全部亲力亲为，因此实在难以抽出时间来更新刷题博客。这个项目中运用到的技术也很广泛，总结了一下，大概包括以下内容：

SpringBoot，SpringSecurity，MyBatis，MyBatisGenerator，PageHelper，Swagger，Hibernator-Validator，Elasticsearch，RabbitMQ，Redis，MongoDB，Docker，Druid，OSS，JWT，LogStash，Lombok

Vue，Vue-router，Vuex，Element，Axios，v-charts，Js-cookie，nprogress

Android，iOS，MVVM，rx等

如果有时间的话，也很想和大家分享一下目前这个私活中学到的一些知识，希望能对大家有所帮助。虽然项目很忙，但今后我还会每周参加leetcode周赛，并尽量保持每周更新一些周赛题目的讲解。此外本网站的题目还会保持更新，大家可以随时查看leetcode每道题目的公司tag以及加锁题目内容。以下言归正传：

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1582

解题思路分析：

这道题难度不大，暴力解是可行的，算法优化可以在暴力解的基础上进行改进即可。

理论上我们循环每一个点，如果当前点是0的话跳过，是1的话我们在查看当前行与列上其他点是否都为0即可。优化的点就在于查看当前行与列这一步上。如果每一个点都查看一遍显然效率很低，因此我们可以将数据提前做一个预处理，即先统计出每一行与每一列上数字1的个数。这样一来循环到当前点时，如果是1，并且当前行与列上的1的个数也都是1的话，那么当前点即是特殊位置，返回结果加一即可。

实现代码：

public int numSpecial(int[][] mat) {
    int[] matR=new int[mat.length];
    for(int r=0;r<mat.length;r++){ // 统计每一行中数字1的个数
        for(int c=0;c<mat[0].length;c++){
            if(mat[r][c]==1) matR[r]++;
        }
    }
    int[] matC=new int[mat[0].length];
    for(int c=0;c<mat[0].length;c++){ // 统计每一列中数字1的个数
        for(int r=0;r<mat.length;r++){
            if(mat[r][c]==1) matC[c]++;
        }
    }
    int res=0;
    for(int r=0;r<mat.length;r++){ // 循环每一个点
        for(int c=0;c<mat[0].length;c++){
            // 如果当前点是1，并且当前行与列中1的个数都是1，返回结果加一
            if(mat[r][c]==1&&matR[r]==1&&matC[c]==1) res++;
        }
    }
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Special Positions in a Binary Matrix.

Memory Usage: 39.5 MB, less than 75.00% of J

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1582-special-positions-in-a-binary-matrix-解题思路分析/