登录
[Python3/Java/C++/Go/TypeScript] 一题一解：哈希表 + 排序（清晰题解）
2025年12月11日 07:16
方法一：哈希表 + 排序
我们可以将建筑按照横坐标和纵坐标进行分组，分别记录在哈希表 $\text{g1}$ 和 $\text{g2}$ 中，其中 $\text{g1[x]}$ 表示所有横坐标为 $x$ 的纵坐标，而 $\text{g2[y]}$ 表示所有纵坐标为 $y$ 的横坐标，然后我们将其进行排序。
接下来，我们遍历所有建筑，对于当前建筑 $(x, y)$，我们通过哈希表获取对应的纵坐标列表 $l_1$ 和横坐标列表 $l_2$，并检查条件以确定建筑是否被覆盖。覆盖的条件是 $l_2[0] < x < l_2[-1]$ 且 $l_1[0] < y < l_1[-1]$，若是，我们将答案加一。
遍历结束后，返回答案即可。
###python
class Solution:
def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
g1 = defaultdict(list)
g2 = defaultdict(list)
for x, y in buildings:
g1[x].append(y)
g2[y].append(x)
for x in g1:
g1[x].sort()
for y in g2:
g2[y].sort()
ans = 0
for x, y in buildings:
l1 = g1[x]
l2 = g2[y]
if l2[0] < x < l2[-1] and l1[0] < y < l1[-1]:
ans += 1
return ans
###java
class Solution {
public int countCoveredBuildings(int n, int[][] buildings) {
Map<Integer, List<Integer>> g1 = new HashMap<>();
Map<Integer, List<Integer>> g2 = new HashMap<>();
for (int[] building : buildings) {
int x = building[0], y = building[1];
g1.computeIfAbsent(x, k -> new ArrayList<>()).add(y);
g2.computeIfAbsent(y, k -> new ArrayList<>()).add(x);
}
for (var e : g1.entrySet()) {
Collections.sort(e.getValue());
}
for (var e : g2.entrySet()) {
Collections.sort(e.getValue());
}
int ans = 0;
for (int[] building : buildings) {
int x = building[0], y = building[1];
List<Integer> l1 = g1.get(x);
List<Integer> l2 = g2.get(y);
if (l2.get(0) < x && x < l2.get(l2.size() - 1) && l1.get(0) < y
&& y < l1.get(l1.size() - 1)) {
ans++;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
unordered_map<int, vector<int>> g1;
unordered_map<int, vector<int>> g2;
for (const auto& building : buildings) {
int x = building[0], y = building[1];
g1[x].push_back(y);
g2[y].push_back(x);
}
for (auto& e : g1) {
sort(e.second.begin(), e.second.end());
}
for (auto& e : g2) {
sort(e.second.begin(), e.second.end());
}
int ans = 0;
for (const auto& building : buildings) {
int x = building[0], y = building[1];
const vector<int>& l1 = g1[x];
const vector<int>& l2 = g2[y];
if (l2[0] < x && x < l2[l2.size() - 1] && l1[0] < y && y < l1[l1.size() - 1]) {
ans++;
}
}
return ans;
}
};
###go
func countCoveredBuildings(n int, buildings [][]int) (ans int) {
g1 := make(map[int][]int)
g2 := make(map[int][]int)
for _, building := range buildings {
x, y := building[0], building[1]
g1[x] = append(g1[x], y)
g2[y] = append(g2[y], x)
}
for _, list := range g1 {
sort.Ints(list)
}
for _, list := range g2 {
sort.Ints(list)
}
for _, building := range buildings {
x, y := building[0], building[1]
l1 := g1[x]
l2 := g2[y]
if l2[0] < x && x < l2[len(l2)-1] && l1[0] < y && y < l1[len(l1)-1] {
ans++
}
}
return
}
###ts
function countCoveredBuildings(n: number, buildings: number[][]): number {
const g1: Map<number, number[]> = new Map();
const g2: Map<number, number[]> = new Map();
for (const [x, y] of buildings) {
if (!g1.has(x)) g1.set(x, []);
g1.get(x)?.push(y);
if (!g2.has(y)) g2.set(y, []);
g2.get(y)?.push(x);
}
for (const list of g1.values()) {
list.sort((a, b) => a - b);
}
for (const list of g2.values()) {
list.sort((a, b) => a - b);
}
let ans = 0;
for (const [x, y] of buildings) {
const l1 = g1.get(x)!;
const l2 = g2.get(y)!;
if (l2[0] < x && x < l2[l2.length - 1] && l1[0] < y && y < l1[l1.length - 1]) {
ans++;
}
}
return ans;
}
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是建筑物的数量。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
