题目描述:
LeetCode 750. Number Of Corner Rectangles
Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
A corner rectangle is 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:
Input: grid = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]] Output: 1 Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Example 2:
Input: grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] Output: 9 Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.
Example 3:
Input: grid = [[1, 1, 1, 1]] Output: 0 Explanation: Rectangles must have four distinct corners.
Note:
- The number of rows and columns of
grid
will each be in the range[1, 200]
. - Each
grid[i][j]
will be either0
or1
. - The number of
1
s in the grid will be at most6000
.
题目大意:
求矩阵grid中所有四角为1的子矩阵的个数(四个角坐标必须互不相同)
解题思路:
朴素解法是枚举左上角和右下角坐标,时间复杂度 O(m^2 * n^2),会导致TLE
组合(Combination)时间复杂度 O(m^2 * n)
枚举起始行x,终止行y: 遍历各列z,统计满足grid[x][z] == 1并且grid[y][z] == 1条件的列数,记为cnt 根据组合公式,C(cnt, 2) = cnt * (cnt - 1) / 2,累加至答案。
Java代码:
class Solution {
public int countCornerRectangles(int[][] grid) {
int m = grid.length, n = grid[0].length;
int ans = 0;
for (int x = 0; x < m; x++) {
for (int y = x + 1; y < m; y++) {
int cnt = 0;
for (int z = 0; z < n; z++) {
if (grid[x][z] == 1 && grid[y][z] == 1) {
cnt++;
}
}
ans += cnt * (cnt - 1) / 2;
}
}
return ans;
}
}
本文链接:http://bookshadow.com/weblog/2017/12/17/leetcode-number-of-corner-rectangles/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。