LeetCode 750. 角矩形的数量
题目描述
题意分析
统计四个角都为
1、边与矩阵行列平行的矩形。四个角必须是不同位置，所以要选择两条不同的行和两条不同的列；矩形内部及边上其他格子的值都不影响合法性。直接枚举两行、两列需要四层循环。先固定上下两行后，可以把满足条件的列合并计数，用组合数一次算出这一行对产生的所有矩形。
解法：枚举行对 + 组合计数
核心思路
[!blue]
固定
r1 < r2作为矩形的上下边。如果某一列c上的grid[r1][c]和grid[r2][c]都为1，这一列就能作为矩形的一条竖边。扫描所有列，用common记录这样的公共列有多少条。任选两条不同的公共列，四个交点就全为
1，能够组成一个合法矩形。反过来，这两行之间的合法矩形也必须选取两条公共列。因此矩形数就是从common条列中选两条的组合数：先计有顺序的选择common * (common - 1)，再除以2去掉左右交换产生的重复。
common只属于当前这一对行，每次更换r2都要重新从零统计。上下行只枚举r1 < r2，而列对已经由组合数去重，所以每个矩形只会在自己唯一的行对、列对中被计算一次。
解题步骤
- 枚举上、下两行。
- 重新统计两行共同为一的列数。
- 用选二组合数累加矩形数量。
只有一行时没有可枚举的行对；只有一列或公共列不足两条时，组合数自然为零。题目行列数都不超过
200，即使把所有位置都当作1，矩形数也至多为 $\binom{200}{2}^2 = 396010000$，可以用int累加。
代码实现
class Solution {
public int countCornerRectangles(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int answer = 0;
for (int r1 = 0; r1 < m; r1++) {
for (int r2 = r1 + 1; r2 < m; r2++) {
// 每对行独立统计共同为一的列
int common = 0;
for (int c = 0; c < n; c++) {
if (grid[r1][c] == 1 && grid[r2][c] == 1) {
common++;
}
}
// 从公共列中选两个，先乘后除避免奇数截断
answer += common * (common - 1) / 2;
}
}
return answer;
}
}
func countCornerRectangles(grid [][]int) int {
m := len(grid)
n := len(grid[0])
answer := 0
for r1 := 0; r1 < m; r1++ {
for r2 := r1 + 1; r2 < m; r2++ {
// 每对行独立统计共同为一的列
common := 0
for c := 0; c < n; c++ {
if grid[r1][c] == 1 && grid[r2][c] == 1 {
common++
}
}
// 从公共列中选两个，先乘后除避免奇数截断
answer += common * (common - 1) / 2
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(m^2n)$，每对行扫描 n 列。
- 空间复杂度：$O(1)$，只用计数变量。
关键点总结
[!green]
- 角点条件与内部填满是不同题目。
- 组合公式已排除同列自配，不需要额外去重。
易错点总结
[!yellow]
- 只检查两行该列数值相等，会将两个零也当作角。
- 重复枚举行对两个方向，会重复计算矩形。
- 组合数先除二再乘，公共列数为奇数时会截断少算。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 939. 最小面积矩形 | 中等 | 同样通过两列在不同行重复出现来确定矩形，原题找最小面积，本题统计数量。 |
| 311. 稀疏矩阵的乘法 | 中等 | 同样利用行之间共享的非零列索引，避免对全矩阵位置做无效组合。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！