登录3531. 统计被覆盖的建筑
解法一
思路和算法
根据建筑被覆盖的定义，当一个建筑在四个方向都至少存在一个其他建筑时，该建筑被覆盖。为了计算被覆盖的建筑数量，需要分别判断每个建筑是否被覆盖，因此需要分别统计每个 $x$ 坐标和每个 $y$ 坐标的所有建筑的列表。
使用两个哈希表分别记录每个 $x$ 坐标的所有建筑列表和每个 $y$ 坐标的所有建筑列表，两个哈希表分别为 $x$ 分组哈希表和 $y$ 分组哈希表。遍历数组 $\textit{buildings}$ 将所有建筑加入两个哈希表，然后将两个哈希表中的每个 $x$ 坐标和 $y$ 坐标对应的建筑列表排序，排序方法如下：在 $x$ 分组哈希表中，将每个 $x$ 坐标的所有建筑列表按 $y$ 坐标升序排序；在 $y$ 分组哈希表中，将每个 $y$ 坐标的所有建筑列表按 $x$ 坐标升序排序。
排序结束之后，即可判断每个建筑在 $x$ 坐标方向和 $y$ 坐标方向是否被覆盖。遍历所有建筑，对于位于坐标 $(x, y)$ 的建筑，判断方法如下。
-
从 $y$ 分组哈希表中得到该建筑的相同 $y$ 坐标的所有建筑的列表，列表已经按 $x$ 坐标升序排序，判断当前 $x$ 坐标是否为列表中的最小值或最大值，如果既不是最小值也不是最大值，则该建筑在 $x$ 坐标方向被覆盖。
-
从 $x$ 分组哈希表中得到该建筑的相同 $x$ 坐标的所有建筑的列表，列表已经按 $y$ 坐标升序排序，判断当前 $y$ 坐标是否为列表中的最小值或最大值，如果既不是最小值也不是最大值，则该建筑在 $y$ 坐标方向被覆盖。
当一个建筑同时在 $x$ 坐标方向和 $y$ 坐标方向被覆盖时，该建筑被覆盖。
遍历结束之后，即可得到被覆盖的建筑数量。
代码
###Java
class Solution {
public int countCoveredBuildings(int n, int[][] buildings) {
Map<Integer, List<Integer>> xToBuildings = new HashMap<Integer, List<Integer>>();
Map<Integer, List<Integer>> yToBuildings = new HashMap<Integer, List<Integer>>();
for (int[] building : buildings) {
int x = building[0], y = building[1];
xToBuildings.putIfAbsent(x, new ArrayList<Integer>());
xToBuildings.get(x).add(y);
yToBuildings.putIfAbsent(y, new ArrayList<Integer>());
yToBuildings.get(y).add(x);
}
Set<Map.Entry<Integer, List<Integer>>> xEntries = xToBuildings.entrySet();
Set<Map.Entry<Integer, List<Integer>>> yEntries = yToBuildings.entrySet();
for (Map.Entry<Integer, List<Integer>> entry : xEntries) {
Collections.sort(entry.getValue());
}
for (Map.Entry<Integer, List<Integer>> entry : yEntries) {
Collections.sort(entry.getValue());
}
int count = 0;
for (int[] building : buildings) {
int x = building[0], y = building[1];
List<Integer> xList = yToBuildings.get(y);
List<Integer> yList = xToBuildings.get(x);
int xMin = xList.get(0), xMax = xList.get(xList.size() - 1);
int yMin = yList.get(0), yMax = yList.get(yList.size() - 1);
if (x > xMin && x < xMax && y > yMin && y < yMax) {
count++;
}
}
return count;
}
}
###C#
public class Solution {
public int CountCoveredBuildings(int n, int[][] buildings) {
IDictionary<int, IList<int>> xToBuildings = new Dictionary<int, IList<int>>();
IDictionary<int, IList<int>> yToBuildings = new Dictionary<int, IList<int>>();
foreach (int[] building in buildings) {
int x = building[0], y = building[1];
xToBuildings.TryAdd(x, new List<int>());
xToBuildings[x].Add(y);
yToBuildings.TryAdd(y, new List<int>());
yToBuildings[y].Add(x);
}
foreach (KeyValuePair<int, IList<int>> pair in xToBuildings) {
((List<int>) pair.Value).Sort();
}
foreach (KeyValuePair<int, IList<int>> pair in yToBuildings) {
((List<int>) pair.Value).Sort();
}
int count = 0;
foreach (int[] building in buildings) {
int x = building[0], y = building[1];
IList<int> xIList = yToBuildings[y];
IList<int> yIList = xToBuildings[x];
int xMin = xIList[0], xMax = xIList[xIList.Count - 1];
int yMin = yIList[0], yMax = yIList[yIList.Count - 1];
if (x > xMin && x < xMax && y > yMin && y < yMax) {
count++;
}
}
return count;
}
}
复杂度分析
-
时间复杂度：$O(m \log m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。将所有建筑存入两个哈希表的时间是 $O(m)$，排序的时间是 $O(m \log m)$，排序之后计算被覆盖的建筑数量的时间是 $O(m)$，因此时间复杂度是 $O(m \log m)$。
-
空间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。哈希表的空间是 $O(m)$。
解法二
思路和算法
判断一个建筑是否被覆盖时，需要知道如下信息。
-
在相同 $y$ 坐标的所有建筑的列表中，该建筑的 $x$ 坐标是否为列表中的最小值或最大值。
-
在相同 $x$ 坐标的所有建筑的列表中，该建筑的 $y$ 坐标是否为列表中的最小值或最大值。
因此，不需要维护每个 $x$ 坐标和每个 $y$ 坐标的所有建筑，只需要维护每个 $x$ 坐标的最小 $y$ 坐标和最大 $y$ 坐标，以及每个 $y$ 坐标的最小 $x$ 坐标和最大 $x$ 坐标。遍历数组 $\textit{buildings}$ 之后，将最小坐标与最大坐标的信息存入哈希表。再次遍历数组，即可根据哈希表中的最小坐标与最大坐标的信息判断每个建筑是否被覆盖，计算被覆盖的建筑数量。
代码
###Java
class Solution {
public int countCoveredBuildings(int n, int[][] buildings) {
Map<Integer, int[]> xToMinMax = new HashMap<Integer, int[]>();
Map<Integer, int[]> yToMinMax = new HashMap<Integer, int[]>();
for (int[] building : buildings) {
int x = building[0], y = building[1];
xToMinMax.putIfAbsent(x, new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE});
int[] yMinMax = xToMinMax.get(x);
yMinMax[0] = Math.min(yMinMax[0], y);
yMinMax[1] = Math.max(yMinMax[1], y);
yToMinMax.putIfAbsent(y, new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE});
int[] xMinMax = yToMinMax.get(y);
xMinMax[0] = Math.min(xMinMax[0], x);
xMinMax[1] = Math.max(xMinMax[1], x);
}
int count = 0;
for (int[] building : buildings) {
int x = building[0], y = building[1];
int[] xMinMax = yToMinMax.get(y);
int[] yMinMax = xToMinMax.get(x);
int xMin = xMinMax[0], xMax = xMinMax[1];
int yMin = yMinMax[0], yMax = yMinMax[1];
if (x > xMin && x < xMax && y > yMin && y < yMax) {
count++;
}
}
return count;
}
}
###C#
public class Solution {
public int CountCoveredBuildings(int n, int[][] buildings) {
IDictionary<int, int[]> xToMinMax = new Dictionary<int, int[]>();
IDictionary<int, int[]> yToMinMax = new Dictionary<int, int[]>();
foreach (int[] building in buildings) {
int x = building[0], y = building[1];
xToMinMax.TryAdd(x, new int[]{int.MaxValue, int.MinValue});
int[] yMinMax = xToMinMax[x];
yMinMax[0] = Math.Min(yMinMax[0], y);
yMinMax[1] = Math.Max(yMinMax[1], y);
yToMinMax.TryAdd(y, new int[]{int.MaxValue, int.MinValue});
int[] xMinMax = yToMinMax[y];
xMinMax[0] = Math.Min(xMinMax[0], x);
xMinMax[1] = Math.Max(xMinMax[1], x);
}
int count = 0;
foreach (int[] building in buildings) {
int x = building[0], y = building[1];
int[] xMinMax = yToMinMax[y];
int[] yMinMax = xToMinMax[x];
int xMin = xMinMax[0], xMax = xMinMax[1];
int yMin = yMinMax[0], yMax = yMinMax[1];
if (x > xMin && x < xMax && y > yMin && y < yMax) {
count++;
}
}
return count;
}
}
复杂度分析
-
时间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。遍历所有建筑维护两个哈希表的时间是 $O(m)$，计算被覆盖的建筑数量的时间是 $O(m)$，因此时间复杂度是 $O(m)$。
-
空间复杂度：$O(m)$，其中 $m$ 是数组 $\textit{buildings}$ 的长度。哈希表的空间是 $O(m)$。
