Medium

题目描述

给你一个二维布尔矩阵 grid。

如果 grid 的 3 个元素满足以下条件，则它们形成一个直角三角形：

  • 其中一个元素与另一个元素在同一行
  • 这个元素与第三个元素在同一列
  • 这 3 个元素可以不相邻

返回可以由 grid 中值为 1 的 3 个元素组成的直角三角形的数量。

示例 1：

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]
输出：2
解释：有两个由值为 1 的元素组成的直角三角形。注意蓝色的元素不能形成直角三角形，因为这 3 个元素在同一列。

示例 2：

输入：grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
输出：0
解释：没有由值为 1 的元素组成的直角三角形。注意蓝色的元素不能形成直角三角形。

示例 3：

输入：grid = [[1,0,1],[1,0,0],[1,0,0]]
输出：2
解释：有两个由值为 1 的元素组成的直角三角形。

提示：

  • 1 <= grid.length <= 1000
  • 1 <= grid[i].length <= 1000
  • 0 <= grid[i][j] <= 1

解题思路

解题思路

要形成直角三角形，需要找到三个值为1的点，其中一个点作为直角顶点，另外两个点分别与这个顶点在同一行和同一列。

核心观察：对于矩阵中任意一个值为1的点 (i, j)，如果它要作为直角三角形的直角顶点，那么：

  • 在第 i 行中还需要至少一个值为1的点（除了 (i, j) 本身）
  • 在第 j 列中还需要至少一个值为1的点（除了 (i, j) 本身）

算法步骤：

  1. 预处理：统计每一行和每一列中值为1的元素个数
  2. 遍历每个值为1的点 (i, j)
  3. 对于每个这样的点，能够形成的直角三角形数量为：(row[i] - 1) × (col[j] - 1)
    • row[i] - 1：该行中除了当前点外还有多少个1
    • col[j] - 1：该列中除了当前点外还有多少个1
    • 两者相乘就是以 (i, j) 为直角顶点能形成的直角三角形数量

这个方法的时间复杂度为 O(mn)，空间复杂度为 O(m+n)，其中 m 和 n 分别是矩阵的行数和列数。

代码实现

class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[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 (grid[i][j] == 1) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }
        
        long long result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    result += (long long)(rowCount[i] - 1) * (colCount[j] - 1);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row_count = [0] * m
        col_count = [0] * n
        
        # 统计每行每列的1的个数
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    row_count[i] += 1
                    col_count[j] += 1
        
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    result += (row_count[i] - 1) * (col_count[j] - 1)
        
        return result

public class Solution {
    public long NumberOfRightTriangles(int[][] grid) {
        int m = grid.Length, n = grid[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 (grid[i][j] == 1) {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }
        
        long result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    result += (long)(rowCount[i] - 1) * (colCount[j] - 1);
                }
            }
        }
        
        return result;
    }
}

var numberOfRightTriangles = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    const rowCount = new Array(m).fill(0);
    const colCount = new Array(n).fill(0);
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                rowCount[i]++;
                colCount[j]++;
            }
        }
    }
    
    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                count += (rowCount[i] - 1) * (colCount[j] - 1);
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m × n)
空间复杂度O(m + n)

其中 m 是矩阵的行数，n 是矩阵的列数。时间复杂度主要来自两次遍历矩阵，空间复杂度来自存储每行每列1的个数的数组。