黑格子的数目

难度: Medium

给你两个整数 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 个黑色格子的块的数目。

示例 1：

输入：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] 。

示例 2：

输入：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⁵
2 <= n <= 10⁵
0 <= coordinates.length <= 10⁴
coordinates[i].length == 2
0 <= coordinates[i][0] < m
0 <= coordinates[i][1] < n
coordinates 中的坐标对两两互不相同。

Submission

运行时间: 427 ms

内存: 20.2 MB

class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        ans = [0] * 5
        s = set()
        for x, y in coordinates:
            s.add((x, y))
        for x, y in coordinates:
            if x + 1 < m and y + 1 < n:
                # 左上角一定有  
                count = 1
                if (x + 1, y) in s:
                    count += 1
                if (x, y + 1) in s:
                    count += 1
                if (x + 1, y + 1) in s:
                    count += 1
                ans[count] += 1
            if x + 1 < m and y - 1 >= 0:
                # 位于右上角
                if (x, y - 1) not in s:
                    count = 1
                    if (x + 1, y - 1) in s:
                        count += 1
                    if (x + 1, y) in s:
                        count += 1
                    ans[count] += 1
            if x - 1 >= 0 and y + 1 < n:
                # 位于左下角
                if (x - 1, y) not in s and (x - 1, y + 1) not in s:
                    count = 1
                    if (x, y + 1) in s:
                        count += 1
                    ans[count] += 1
            if x - 1 >= 0 and y - 1 >= 0:
                if (x - 1, y - 1) not in s and (x, y - 1) not in s and (x - 1, y) not in s:
                    ans[1] += 1
        ans[0] = (m - 1) * (n - 1) - sum(ans[1:])
        return ans

Explain

该题解首先使用一个集合s来记录所有黑色格子的坐标，以便于后续判断一个格子是否为黑色。接着，遍历所有的黑色格子坐标，并对每个黑色格子坐标进行四种情况的检查：1) 当前格子作为2x2子矩阵左上角；2) 当前格子作为2x2子矩阵右上角；3) 当前格子作为2x2子矩阵左下角；4) 当前格子作为2x2子矩阵右下角。对于每一种情况，根据黑色格子的存在与否统计每个子矩阵中黑色格子的数量，并更新结果数组ans。最后，通过总2x2子矩阵数量减去包含1个及以上黑色格子的子矩阵的数量，来计算完全由白色格子组成的子矩阵的数量。

时间复杂度: O(k)

空间复杂度: O(k)

class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        ans = [0] * 5  # 存储每种黑格子数量的块的数量
        s = set()  # 存储黑格子坐标
        for x, y in coordinates:
            s.add((x, y))  # 将坐标添加到集合中
        for x, y in coordinates:
            if x + 1 < m and y + 1 < n:  # 检查当前格子是否可以是2x2子矩阵的左上角
                count = 1
                if (x + 1, y) in s:
                    count += 1
                if (x, y + 1) in s:
                    count += 1
                if (x + 1, y + 1) in s:
                    count += 1
                ans[count] += 1
            if x + 1 < m and y - 1 >= 0:  # 检查当前格子是否可以是2x2子矩阵的右上角
                if (x, y - 1) not in s:
                    count = 1
                    if (x + 1, y - 1) in s:
                        count += 1
                    if (x + 1, y) in s:
                        count += 1
                    ans[count] += 1
            if x - 1 >= 0 and y + 1 < n:  # 检查当前格子是否可以是2x2子矩阵的左下角
                if (x - 1, y) not in s and (x - 1, y + 1) not in s:
                    count = 1
                    if (x, y + 1) in s:
                        count += 1
                    ans[count] += 1
            if x - 1 >= 0 and y - 1 >= 0:  # 检查当前格子是否可以是2x2子矩阵的右下角
                if (x - 1, y - 1) not in s and (x, y - 1) not in s and (x - 1, y) not in s:
                    ans[1] += 1
        ans[0] = (m - 1) * (n - 1) - sum(ans[1:])  # 计算全白块的数量
        return ans

Explore

使用集合s检查格子是否为黑色的方法，虽然提供了O(1)时间复杂度的平均查询效率，但在某些特定情况下可能会导致性能瓶颈。当输入的黑色格子坐标数量非常大时，尤其是接近整个网格大小的时候，集合的维护（插入和查询操作）可能会消耗较多的时间和空间。此外，Python中集合的性能还受到负载因子和哈希冲突的影响，当哈希表的负载因子过高或哈希函数产生了较多的冲突时，集合操作的效率会下降。

题解中确实存在重复计算的可能性，尤其是当同一个黑色格子被多次考虑为不同2x2子矩阵角的情况时。例如，一个黑色格子在作为一个子矩阵的左上角被计算后，可能还会作为相邻子矩阵的右上角或左下角等再次被计算。为了减少重复计算，可以通过只从特定方向（如只考虑每个格子作为2x2子矩阵的左上角）来进行计数，这样可以确保每个子矩阵只被计算一次，然后根据需要调整其他角的计数逻辑，确保所有情况被正确计算而不重复。

是的，题解中的逻辑确实存在不更新ans数组的情况，这主要发生在某些边界或角落的格子无法形成完整的2x2子矩阵时。例如，如果一个黑色格子位于网格的边界上，那么它可能无法作为2x2子矩阵的某些角，这导致这些情况下ans数组不被更新。这种情况下，如果没有适当的处理，确实存在漏计的风险。为了避免漏计，需要确保对所有可能形成的2x2子矩阵进行全面的检查和计数，特别是对于边界和角落的格子，要根据其位置调整计数逻辑，确保所有可能的情况都被正确计算。