题目描述
给你两个整数 m
和 n
,表示一个下标从 0 开始的 m x n
的网格图。
给你一个下标从 0 开始的二维整数矩阵 coordinates
,其中 coordinates[i] = [x, y]
表示坐标为 [x, y]
的格子是 黑色的,所有没出现在 coordinates
中的格子都是 白色的。
一个块定义为网格图中 2 x 2
的一个子矩阵。更正式的,对于左上角格子为 [x, y]
的块,其中 0 <= x < m - 1
且 0 <= y < n - 1
,包含坐标为 [x, y]
,[x + 1, y]
,[x, y + 1]
和 [x + 1, y + 1]
的格子。
请你返回一个下标从 0 开始长度为 5
的整数数组 arr
,arr[i]
表示恰好包含 i
个 黑色 格子的块的数目。
样例
输入:m = 3, n = 3, coordinates = [[0,0]]
输出:[3,1,0,0,0]
解释:网格图如下:
只有 1 个块有一个黑色格子,这个块是左上角为 [0,0] 的块。
其他 3 个左上角分别为 [0,1],[1,0] 和 [1,1] 的块都有 0 个黑格子。
所以我们返回 [3,1,0,0,0]。
输入:m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
输出:[0,2,2,0,0]
解释:网格图如下:
有 2 个块有 2 个黑色格子(左上角格子分别为 [0,0] 和 [0,1])。
左上角为 [1,0] 和 [1,1] 的两个块,都有 1 个黑格子。
所以我们返回 [0,2,2,0,0]。
限制
2 <= m <= 10^5
2 <= n <= 10^5
0 <= coordinates.length <= 10^4
coordinates[i].length == 2
0 <= coordinates[i][0] < m
0 <= coordinates[i][1] < n
coordinates
中的坐标对两两互不相同。
算法
(计算贡献) $O(coordiates.length)$
- 对于每个黑格子,都给左上角格子块的贡献加 $1$,最后统计每个左上角的格子的贡献值。
- 具体地,对于黑格子 $(x, y)$,则左上角的格子块 $(x - 1, y - 1), (x, y - 1), (x - 1, y - 1), (x, y)$ 在哈希表中的值增加 $1$。
- 最终统计哈希表的值域,黑色格子为 $0$ 的块可以通过 $(m - 1)(n - 1)$ 减去有黑色格子的块的数目计算得到。
时间复杂度
- 每个黑格子访问周围 $4$ 个格子,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
#define LL long long
const int dx[] = {-1, -1, 0, 0};
const int dy[] = {-1, 0, -1, 0};
class Solution {
public:
vector<LL> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
unordered_map<LL, int> seen;
for (const auto &c : coordinates) {
int x = c[0], y = c[1];
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || tx >= m - 1 || ty < 0 || ty >= n - 1)
continue;
++seen[(LL)(tx) * n + ty];
}
}
vector<LL> ans(5, 0);
for (const auto &[_, v] : seen)
++ans[v];
ans[0] = (LL)(m - 1) * (n - 1) - ans[1] - ans[2] - ans[3] - ans[4];
return ans;
}
};