Medium

题目描述

给定一个正整数 n，表示一个 n x n 的城市。还给定一个二维网格 buildings，其中 buildings[i] = [x, y] 表示位于坐标 [x, y] 的一个唯一建筑物。

如果一个建筑物在所有四个方向（左、右、上、下）都至少有一个建筑物，则该建筑物被覆盖。

返回被覆盖的建筑物数量。

示例 1：

输入：n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]
输出：1
解释：
只有建筑物 [2,2] 被覆盖，因为它在四个方向都有至少一个建筑物：
- 上方 ([1,2])
- 下方 ([3,2])  
- 左方 ([2,1])
- 右方 ([2,3])
因此，被覆盖的建筑物数量为 1。

示例 2：

输入：n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
输出：0
解释：
没有建筑物在四个方向都有建筑物。

示例 3：

输入：n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]
输出：1
解释：
只有建筑物 [3,3] 被覆盖，因为它在四个方向都有至少一个建筑物：
- 上方 ([1,3])
- 下方 ([5,3])
- 左方 ([3,2])
- 右方 ([3,5])
因此，被覆盖的建筑物数量为 1。

约束条件：

  • 2 <= n <= 10^5
  • 1 <= buildings.length <= 10^5
  • buildings[i] = [x, y]
  • 1 <= x, y <= n
  • 所有建筑物的坐标都是唯一的。

解题思路

这道题需要判断每个建筑物在四个方向（上下左右）是否都有其他建筑物。关键思路是：

基本思路： 一个建筑物被覆盖的条件是在同一行和同一列都不是边界建筑。具体来说：

  • 在同一行中，不是最左边或最右边的建筑物
  • 在同一列中，不是最上面或最下面的建筑物

优化解法：

  1. 按行分组：将所有建筑物按行（x坐标）分组，对每行的y坐标排序
  2. 按列分组：将所有建筑物按列（y坐标）分组，对每列的x坐标排序
  3. 标记覆盖状态：
    • 对于每行，标记不在首尾位置的建筑物为"行覆盖"
    • 对于每列，标记不在首尾位置的建筑物为"列覆盖"
  4. 统计结果：只有同时满足"行覆盖"和"列覆盖"的建筑物才是被完全覆盖的

这种方法的优势是只需要对每个方向排序一次，然后用集合操作找到同时满足两个条件的建筑物，时间复杂度较低。

代码实现

class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        unordered_map<int, vector<int>> rows, cols;
        
        // Group buildings by row and column
        for (auto& building : buildings) {
            rows[building[0]].push_back(building[1]);
            cols[building[1]].push_back(building[0]);
        }
        
        // Sort each group
        for (auto& [x, ys] : rows) {
            sort(ys.begin(), ys.end());
        }
        for (auto& [y, xs] : cols) {
            sort(xs.begin(), xs.end());
        }
        
        set<pair<int, int>> rowCovered, colCovered;
        
        // Find buildings covered in rows (not first or last in their row)
        for (auto& [x, ys] : rows) {
            if (ys.size() > 2) {
                for (int i = 1; i < ys.size() - 1; i++) {
                    rowCovered.insert({x, ys[i]});
                }
            }
        }
        
        // Find buildings covered in columns (not first or last in their column)
        for (auto& [y, xs] : cols) {
            if (xs.size() > 2) {
                for (int i = 1; i < xs.size() - 1; i++) {
                    colCovered.insert({xs[i], y});
                }
            }
        }
        
        // Count buildings covered in both directions
        int count = 0;
        for (auto& building : rowCovered) {
            if (colCovered.count(building)) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        from collections import defaultdict
        
        rows = defaultdict(list)
        cols = defaultdict(list)
        
        # Group buildings by row and column
        for x, y in buildings:
            rows[x].append(y)
            cols[y].append(x)
        
        # Sort each group
        for ys in rows.values():
            ys.sort()
        for xs in cols.values():
            xs.sort()
        
        row_covered = set()
        col_covered = set()
        
        # Find buildings covered in rows (not first or last in their row)
        for x, ys in rows.items():
            if len(ys) > 2:
                for i in range(1, len(ys) - 1):
                    row_covered.add((x, ys[i]))
        
        # Find buildings covered in columns (not first or last in their column)
        for y, xs in cols.items():
            if len(xs) > 2:
                for i in range(1, len(xs) - 1):
                    col_covered.add((xs[i], y))
        
        # Count buildings covered in both directions
        return len(row_covered & col_covered)

public class Solution {
    public int CountCoveredBuildings(int n, int[][] buildings) {
        var rows = new Dictionary<int, List<int>>();
        var cols = new Dictionary<int, List<int>>();
        
        // Group buildings by row and column
        foreach (var building in buildings) {
            int x = building[0], y = building[1];
            if (!rows.ContainsKey(x)) rows[x] = new List<int>();
            if (!cols.ContainsKey(y)) cols[y] = new List<int>();
            rows[x].Add(y);
            cols[y].Add(x);
        }
        
        // Sort each group
        foreach (var ys in rows.Values) {
            ys.Sort();
        }
        foreach (var xs in cols.Values) {
            xs.Sort();
        }
        
        var rowCovered = new HashSet<(int, int)>();
        var colCovered = new HashSet<(int, int)>();
        
        // Find buildings covered in rows (not first or last in their row)
        foreach (var kvp in rows) {
            int x = kvp.Key;
            var ys = kvp.Value;
            if (ys.Count > 2) {
                for (int i = 1; i < ys.Count - 1; i++) {
                    rowCovered.Add((x, ys[i]));
                }
            }
        }
        
        // Find buildings covered in columns (not first or last in their column)
        foreach (var kvp in cols) {
            int y = kvp.Key;
            var xs = kvp.Value;
            if (xs.Count > 2) {
                for (int i = 1; i < xs.Count - 1; i++) {
                    colCovered.Add((xs[i], y));
                }
            }
        }
        
        // Count buildings covered in both directions
        int count = 0;
        foreach (var building in rowCovered) {
            if (colCovered.Contains(building)) {
                count++;
            }
        }
        
        return count;
    }
}

var countCoveredBuildings = function(n, buildings) {
    const rows = new Map();
    const cols = new Map();
    
    // Group buildings by row and column
    for (const [x, y] of buildings) {
        if (!rows.has(x)) rows.set(x, []);
        if (!cols.has(y)) cols.set(y, []);
        rows.get(x).push(y);
        cols.get(y).push(x);
    }
    
    // Sort each group
    for (const ys of rows.values()) {
        ys.sort((a, b) => a - b);
    }
    for (const xs of cols.values()) {
        xs.sort((a, b) => a - b);
    }
    
    const rowCovered = new Set();
    const colCovered = new Set();
    
    // Find buildings covered in rows (not first or last in their row)
    for (const [x, ys] of rows) {
        if (ys.length > 2) {
            for (let i = 1; i < ys.length - 1; i++) {
                rowCovered.add(`${x},${ys[i]}`);
            }
        }
    }
    
    // Find buildings covered in columns (not first or last in their column)
    for (const [y, xs] of cols) {
        if (xs.length > 2) {
            for (let i = 1; i < xs.length - 1; i++) {
                colCovered.add(`${xs[i]},${y}`);
            }
        }
    }
    
    // Count buildings covered in both directions
    let count = 0;
    for (const building of rowCovered) {
        if (colCovered.has(building)) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(m log m)
空间复杂度O(m)

其中 m 是建筑物的数量。时间复杂度主要由排序操作决定，空间复杂度用于存储分组后的建筑物和覆盖状态集合。