Easy

题目描述

给你一个 m x n 的二进制矩阵 mat，请你返回矩阵 mat 中特殊位置的数目。

如果位置 (i, j) 满足 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 且所在的第1行和第2列的其他元素都是 0

示例 2：

输入：mat = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解释：(0,0), (1,1) 和 (2,2) 都是特殊位置

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • mat[i][j] 是 0 或 1

解题思路

解题思路

这道题的关键在于理解特殊位置的定义：位置 (i,j) 是特殊位置当且仅当该位置值为1，且该位置所在的行和列都只有这一个1。

方法一：预处理统计（推荐） 首先统计每行和每列中1的个数，然后遍历矩阵。对于每个值为1的位置，检查其所在行和列是否都只有一个1。

算法流程：

  1. 遍历矩阵，统计每行中1的个数存储在 rowCount 数组中
  2. 统计每列中1的个数存储在 colCount 数组中
  3. 再次遍历矩阵，对于每个 mat[i][j] == 1 的位置：
    • 如果 rowCount[i] == 1 且 colCount[j] == 1，则该位置是特殊位置
  4. 返回特殊位置的总数

方法二：直接验证 对于每个值为1的位置，直接检查其所在行和列是否只有这一个1。时间复杂度较高但逻辑简单。

预处理方法的优势在于避免了重复计算，时间复杂度更优，是推荐解法。

代码实现

class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<int> rowCount(m, 0), colCount(n, 0);
        
        // 统计每行每列的1的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }
        
        int result = 0;
        // 检查特殊位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1 && rowCount[i] == 1 && colCount[j] == 1) {
                    result++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        row_count = [0] * m
        col_count = [0] * n
        
        # 统计每行每列的1的个数
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    row_count[i] += 1
                    col_count[j] += 1
        
        result = 0
        # 检查特殊位置
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1 and row_count[i] == 1 and col_count[j] == 1:
                    result += 1
        
        return result

public class Solution {
    public int NumSpecial(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        int[] rowCount = new int[m];
        int[] colCount = new int[n];
        
        // 统计每行每列的1的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }
        
        int result = 0;
        // 检查特殊位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1 && rowCount[i] == 1 && colCount[j] == 1) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

var numSpecial = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    let count = 0;
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 1) {
                let rowSum = mat[i].reduce((sum, val) => sum + val, 0);
                let colSum = 0;
                for (let k = 0; k < m; k++) {
                    colSum += mat[k][j];
                }
                
                if (rowSum === 1 && colSum === 1) {
                    count++;
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型预处理方法直接验证方法
时间复杂度O(m×n)O(m×n×(m+n))
空间复杂度O(m+n)O(1)

相关题目