Medium

题目描述

给你两个整数 m 和 n，表示一个下标从 0 开始的 m x n 网格的维数。

同时给你一个下标从 0 开始的二维整数矩阵 coordinates，其中 coordinates[i] = [x, y] 表示坐标为 [x, y] 的单元格是黑色的，格网中所有其他单元格都是白色的。

一个块定义为网格中的一个 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] 开始。它们都有零个黑色单元格。
因此，我们返回 [3,1,0,0,0]。

示例 2：

输入：m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
输出：[0,2,2,0,0]
解释：网格如下所示：

有 2 个块包含两个黑色单元格（从单元格坐标 [0,0] 和 [0,1] 开始的块）。
其他 2 个块的起始单元格坐标为 [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 中的坐标都是成对不同的。

解题思路

这道题的关键是理解：虽然总的块数量很大（(m-1) * (n-1)），但包含黑色格子的块数量相对较少，我们只需要关注这些块。

核心思路：

  1. 每个黑色格子最多影响 4 个不同的 2x2 块（作为左上、左下、右上、右下角）
  2. 使用哈希表记录每个块包含的黑色格子数量
  3. 统计各种情况的块数量

具体步骤：

  1. 遍历所有黑色格子坐标
  2. 对于每个黑色格子 (x, y)，找出包含它的所有 2x2 块：
    • 以 (x-1, y-1) 为左上角的块（如果存在）
    • 以 (x-1, y) 为左上角的块（如果存在）
    • 以 (x, y-1) 为左上角的块（如果存在）
    • 以 (x, y) 为左上角的块（如果存在）
  3. 在哈希表中记录每个块的黑色格子数量
  4. 统计结果：包含 0 个黑色格子的块数 = 总块数 - 哈希表中的块数

时间复杂度优化： 由于黑色格子数量最多 10^4，每个格子最多影响 4 个块，所以受影响的块数量最多 4 * 10^4，远小于总块数 10^10。

代码实现

class Solution {
public:
    vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
        unordered_map<long long, int> blockCount;
        
        for (auto& coord : coordinates) {
            int x = coord[0], y = coord[1];
            
            // 检查包含当前黑色格子的所有可能的2x2块
            for (int dx = -1; dx <= 0; dx++) {
                for (int dy = -1; dy <= 0; dy++) {
                    int blockX = x + dx;
                    int blockY = y + dy;
                    
                    // 检查块是否在有效范围内
                    if (blockX >= 0 && blockX < m - 1 && blockY >= 0 && blockY < n - 1) {
                        long long key = (long long)blockX * n + blockY;
                        blockCount[key]++;
                    }
                }
            }
        }
        
        vector<long long> result(5, 0);
        
        // 统计各种黑色格子数量的块
        for (auto& p : blockCount) {
            result[p.second]++;
        }
        
        // 计算包含0个黑色格子的块数量
        long long totalBlocks = (long long)(m - 1) * (n - 1);
        result[0] = totalBlocks - blockCount.size();
        
        return result;
    }
};

class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        block_count = {}
        
        for x, y in coordinates:
            # 检查包含当前黑色格子的所有可能的2x2块
            for dx in [-1, 0]:
                for dy in [-1, 0]:
                    block_x = x + dx
                    block_y = y + dy
                    
                    # 检查块是否在有效范围内
                    if 0 <= block_x < m - 1 and 0 <= block_y < n - 1:
                        key = (block_x, block_y)
                        block_count[key] = block_count.get(key, 0) + 1
        
        result = [0] * 5
        
        # 统计各种黑色格子数量的块
        for count in block_count.values():
            result[count] += 1
        
        # 计算包含0个黑色格子的块数量
        total_blocks = (m - 1) * (n - 1)
        result[0] = total_blocks - len(block_count)
        
        return result

public class Solution {
    public long[] CountBlackBlocks(int m, int n, int[][] coordinates) {
        Dictionary<long, int> blockCount = new Dictionary<long, int>();
        
        foreach (var coord in coordinates) {
            int x = coord[0], y = coord[1];
            
            // 检查包含当前黑色格子的所有可能的2x2块
            for (int dx = -1; dx <= 0; dx++) {
                for (int dy = -1; dy <= 0; dy++) {
                    int blockX = x + dx;
                    int blockY = y + dy;
                    
                    // 检查块是否在有效范围内
                    if (blockX >= 0 && blockX < m - 1 && blockY >= 0 && blockY < n - 1) {
                        long key = (long)blockX * n + blockY;
                        blockCount[key] = blockCount.GetValueOrDefault(key, 0) + 1;
                    }
                }
            }
        }
        
        long[] result = new long[5];
        
        // 统计各种黑色格子数量的块
        foreach (var count in blockCount.Values) {
            result[count]++;
        }
        
        // 计算包含0个黑色格子的块数量
        long totalBlocks = (long)(m - 1) * (n - 1);
        result[0] = totalBlocks - blockCount.Count;
        
        return result;
    }
}

var countBlackBlocks = function(m, n, coordinates) {
    const blockCount = new Map();
    
    for (const [x, y] of coordinates) {
        // 检查包含当前黑色格子的所有可能的2x2块
        for (let dx = -1; dx <= 0; dx++) {
            for (let dy = -1; dy <= 0; dy++) {
                const blockX = x + dx;
                const blockY = y + dy;
                
                // 检查块是否在有效范围内
                if (blockX >= 0 && blockX < m - 1 && blockY >= 0 && blockY < n - 1) {
                    const key = blockX * n + blockY;
                    blockCount.set(key, (blockCount.get(key) || 0) + 1);
                }
            }
        }
    }
    
    const result = [0, 0, 0, 0, 0];
    
    // 统计各种黑色格子数量的块
    for (const count of blockCount.values()) {
        result[count]++;
    }
    
    // 计算包含0个黑色格子的块数量
    const totalBlocks = (m - 1) * (n - 1);
    result[0] = totalBlocks - blockCount.size;
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k)，其中 k 是 coordinates 的长度。每个黑色格子最多影响 4 个块
空间复杂度O(k)，哈希表最多存储 4k 个不同的块