leetcode 2026-03-04 每日一练 - 统计特殊位置

Austoin2026-03-042026-03-04

题目描述

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

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

如果位置 (i, j) 满足 mat[i][j] == 1 并且行 i 与列 j 中的所有其他元素都是 0（行和列的下标从 0 开始计数），那么它被称为特殊位置。

示例：

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

解题思路

核心观察

特殊位置需要同时满足两个条件：

该位置的值为 1
该位置所在的行和列中，只有这一个 1，其他都是 0

优化策略

如果直接暴力检查每个位置，需要对每个 1 都遍历整行整列，时间复杂度会达到 O(m² × n²)。

优化思路：预处理每行和每列的 1 的个数

第一次遍历：统计每行和每列的 1 的总数
第二次遍历：检查每个 1 所在的行和列是否都只有一个 1

这样时间复杂度降低到 O(m × n)。

算法步骤

创建两个数组 rows 和 cols，分别记录每行和每列的 1 的个数
第一次遍历矩阵，统计每行每列的 1 的数量
第二次遍历矩阵，对于每个值为 1 的位置 (i, j)：
- 如果 rows[i] == 1 且 cols[j] == 1，说明这是特殊位置
- 计数器加 1

代码实现

方法一：预处理行列和（推荐）

func numSpecial(mat [][]int) (ans int) {
    m := len(mat)
    if m == 0 {
        return 0
    }
    n := len(mat[0])
    
    // 统计每行和每列的1的个数
    rows := make([]int, m)
    cols := make([]int, n)
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            rows[i] += mat[i][j]
            cols[j] += mat[i][j]
        }
    }
    
    // 检查每个1是否为特殊位置
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1 {
                ans++
            }
        }
    }
    return
}

方法二：记录索引（备选）

func numSpecial(mat [][]int) (ans int) {
    rows, cols := []int{}, []int{}
    
    // 找出只有一个1的行
    for i, row := range mat {
        if sum(row) == 1 {
            rows = append(rows, i)
        }
    }
    
    // 找出只有一个1的列
    for i := 0; i < len(mat[0]); i++ {
        s := 0
        for j := 0; j < len(mat); j++ {
            s += mat[j][i]
        }
        if s == 1 {
            cols = append(cols, i)
        }
    }
    
    // 检查交叉点
    for _, i := range rows {
        for _, j := range cols {
            ans += mat[i][j]
        }
    }
    return
}

func sum(nums []int) (ans int) {
    for _, i := range nums {
        ans += i
    }
    return
}