750 Number Of Corner Rectangles

1. Question

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
Acorner rectangleis 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.
Example 1:
1
Input: grid =
2
[[1, 0, 0, 1, 0],
3
[0, 0, 1, 0, 1],
4
[0, 0, 0, 1, 0],
5
[1, 0, 1, 0, 1]]
6
7
Output: 1
8
9
Explanation:
10
There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Copied!
Example 2:
1
Input: grid =
2
[[1, 1, 1],
3
[1, 1, 1],
4
[1, 1, 1]]
5
6
Output: 9
7
8
Explanation:
9
There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.
Copied!
Example 3:
1
Input: grid =
2
[[1, 1, 1, 1]]
3
4
Output: 0
5
6
Explanation:
7
Rectangles must have four distinct corners.
Copied!
Note:
  1. 1.
    The number of rows and columns ofgridwill each be in the range[1, 200].
  2. 2.
    Eachgrid[i][j]will be either0or1.
  3. 3.
    The number of1s in the grid will be at most6000.

2. Implementation

(1)
思路: 1. 对于任意两行,找出它们在同一列都有1的个数count
2.然后我们从这些count中,任意选择两列作为矩形的边,根据组合公式,n里面取两个,公式为 n * (n - 1) /2
1
class Solution {
2
public int countCornerRectangles(int[][] grid) {
3
if (grid == null || grid.length == 0 || grid[0].length == 0) {
4
return 0;
5
}
6
7
int m = grid.length, n = grid[0].length;
8
9
int count = 0;
10
int res = 0;
11
12
for (int i = 0; i < m; i++) {
13
for (int j = i + 1; j < m; j++) {
14
count = 0;
15
for (int k = 0; k < n; k++) {
16
if (grid[i][k] == 1 && grid[j][k] == 1) {
17
++count;
18
}
19
}
20
res += count * (count - 1) / 2;
21
}
22
}
23
return res;
24
}
25
}
Copied!

3. Time & Space Complexity

时间复杂度O(nm^2),m为矩形的行数,n为矩形的列数,空间复杂度O(1)