leetcode
leetcode 1401 ~ 1450
二进制矩阵中的特殊位置

二进制矩阵中的特殊位置

难度:

标签:

题目描述

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

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

 

示例 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]01

代码结果

运行时间: 31 ms, 内存: 16.5 MB


/*
 * 思路:
 * 使用Java Stream API来简化代码。
 * 对于每个元素为1的位置,使用Stream API检查其所在行和列的其他所有元素是否都为0。
 */
import java.util.stream.IntStream;

public class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        return (int) IntStream.range(0, m).boxed()
            .flatMap(i -> IntStream.range(0, n).filter(j -> mat[i][j] == 1).mapToObj(j -> new int[]{i, j}))
            .filter(pos -> isSpecial(mat, pos[0], pos[1]))
            .count();
    }

    private boolean isSpecial(int[][] mat, int row, int col) {
        return IntStream.range(0, mat[0].length).allMatch(j -> j == col || mat[row][j] == 0) &&
               IntStream.range(0, mat.length).allMatch(i -> i == row || mat[i][col] == 0);
    }
}

解释

方法:

此题解的核心思想是首先遍历每一行,判断行内元素之和是否大于1。如果大于1,则该行不可能含有特殊位置,直接跳过。如果不大于1(即只有一个1或全0),则进一步检查每个为1的元素。对于每一个1,检查其所在列的其他行是否也为1。如果当前列其他行有1,则当前位置不是特殊位置。这个过程中,通过维护一个结果计数器res来记录特殊位置的数量。

时间复杂度:

O(m^2 * n)

空间复杂度:

O(1)

代码细节讲解

🦆
在遍历每行时,你是如何确保即使行元素之和为1时,该元素的列中没有其他的1?
在题解中,当发现某一行的元素之和为1时,会进一步检查该行中为1的元素所在列的其他行是否也为1。这是通过在已经确定行内只有一个1后,对该1所在的列进行遍历检查来实现的。具体操作是遍历该列的所有行,如果除了当前行外发现其他行也有1,则该位置不是特殊位置。这样可以确保即使行元素之和为1,也会进一步验证该1的列中没有其他的1,从而确保其为特殊位置。
🦆
如果一个行内只有一个1,但其对应列中的其他行也有1,这种情况下题解中的逻辑是否仍然有效?
题解中的逻辑对这种情况是有效的。根据题解,当行内元素之和为1时,会先暂时将该位置认为是特殊位置并增加结果计数器,然后检查该1所在列的其他行。如果在该列的其他行也发现1,则会从结果计数器中减去1,即撤销之前的计数。这样可以确保只有当该1所在的列中没有其他的1时,该位置才被最终认定为特殊位置。
🦆
题解中提到,如果行内元素之和大于1则直接跳过,这是否意味着全0行也会被跳过?全0行是否应该被考虑?
根据题解的逻辑,全0行不会被跳过。题解中只会跳过那些行内元素之和大于1的行。对于全0行,由于其元素之和为0,不大于1,因此不会被跳过。然而,全0行不包含任何1,因此也不可能包含特殊位置。尽管全0行会被遍历,但实际上它们不会对结果计数器产生贡献。
🦆
对于内层循环,为什么选择遍历每一列而不是只在发现行的和为1时,直接找到该1的位置并检查其列?
在题解中,确实可以考虑优化方法,只在行的元素之和为1时直接定位到该1的位置,而不是遍历整个行的每个列。这样做能减少不必要的检查,提高效率。根据题解,对每个列的遍历是为了保证代码的通用性和简单性。然而,在实际应用中,优化这一部分可以显著减少运算量,尤其是在矩阵较大时。一旦行的和为1,可以使用例如`index()`函数(在某些编程语言中)直接找到1的位置,然后直接检查该列,这样可以更高效地实现算法。

相关问题