Medium
题目描述
给你一个在 X-Y 平面上的点流。设计一个满足下述要求的算法：
- 添加 新点到数据结构中。允许添加重复的点，并会视作不同的点。
- 给定一个查询点，统计 由数据结构中选出三个点与给定查询点可组成的满足下述条件的轴对齐正方形 的方案数：
- 轴对齐正方形是一个正方形，除了四条边长度相同之外，还满足每条边都与 x-axis 或 y-axis 平行或垂直。
请你实现 DetectSquares 类：
DetectSquares()使用空数据结构初始化对象void add(int[] point)向数据结构添加一个新的点point = [x, y]int count(int[] point)统计按上述方式与点point = [x, y]组成轴对齐正方形的方案数。
示例 1：
输入：
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
输出：
[null, null, null, null, 1, 0, null, 2]
解释：
DetectSquares detectSquares = new DetectSquares();
detectSquares.add([3, 10]);
detectSquares.add([11, 2]);
detectSquares.add([3, 2]);
detectSquares.count([11, 10]); // 返回 1 。你可以选择：
// - 第一个，第二个，和第三个点
detectSquares.count([14, 8]); // 返回 0 。查询点无法与数据结构中的任何点组成正方形。
detectSquares.add([11, 2]); // 允许添加重复的点。
detectSquares.count([11, 10]); // 返回 2 。你可以选择：
// - 第一个，第二个，和第三个点
// - 第一个，第三个，和第四个点
提示：
point.length == 20 <= x, y <= 1000- 调用
add和count的 总次数 最多为3000
解题思路
解题思路
要组成轴对齐正方形，我们需要找到三个点与查询点配对。关键观察是：给定查询点作为正方形的一个顶点，我们可以通过以下步骤找到其他三个顶点：
- 枚举对角顶点：遍历所有已添加的点，将它们作为查询点的对角顶点候选
- 验证是否能构成正方形：对角顶点必须满足
|x1-x2| == |y1-y2|且x1 != x2且y1 != y2 - 寻找另外两个顶点：根据查询点和对角点，计算出另外两个顶点的坐标
- 统计方案数：检查这两个顶点在数据结构中的出现次数，相乘得到当前对角点对应的方案数
具体实现中，我们使用哈希表存储每个点的出现次数。对于查询点 (x1, y1) 和潜在对角点 (x3, y3)，另外两个顶点坐标为 (x1, y3) 和 (x3, y1)。
时间复杂度主要取决于 count 操作，需要遍历所有不同的点。由于坐标范围有限(0-1000)，最多有约100万个不同坐标，但实际点数受调用次数限制。
推荐解法：使用哈希表记录点频次的方法，简洁高效。
代码实现
class DetectSquares {
private:
map<pair<int,int>, int> pointCount;
public:
DetectSquares() {
}
void add(vector<int> point) {
pointCount[{point[0], point[1]}]++;
}
int count(vector<int> point) {
int x1 = point[0], y1 = point[1];
int result = 0;
for (auto& [p, cnt] : pointCount) {
int x3 = p.first, y3 = p.second;
// 检查是否能构成正方形（对角顶点）
if (abs(x1 - x3) == abs(y1 - y3) && x1 != x3 && y1 != y3) {
// 另外两个顶点
int count1 = pointCount[{x1, y3}];
int count2 = pointCount[{x3, y1}];
result += cnt * count1 * count2;
}
}
return result;
}
};
class DetectSquares:
def __init__(self):
from collections import defaultdict
self.point_count = defaultdict(int)
def add(self, point: List[int]) -> None:
self.point_count[tuple(point)] += 1
def count(self, point: List[int]) -> int:
x1, y1 = point
result = 0
for (x3, y3), cnt in self.point_count.items():
# 检查是否能构成正方形（对角顶点）
if abs(x1 - x3) == abs(y1 - y3) and x1 != x3 and y1 != y3:
# 另外两个顶点
count1 = self.point_count[(x1, y3)]
count2 = self.point_count[(x3, y1)]
result += cnt * count1 * count2
return result
public class DetectSquares {
private Dictionary<(int, int), int> pointCount;
public DetectSquares() {
pointCount = new Dictionary<(int, int), int>();
}
public void Add(int[] point) {
var key = (point[0], point[1]);
if (pointCount.ContainsKey(key)) {
pointCount[key]++;
} else {
pointCount[key] = 1;
}
}
public int Count(int[] point) {
int x1 = point[0], y1 = point[1];
int result = 0;
foreach (var kvp in pointCount) {
int x3 = kvp.Key.Item1, y3 = kvp.Key.Item2;
int cnt = kvp.Value;
// 检查是否能构成正方形（对角顶点）
if (Math.Abs(x1 - x3) == Math.Abs(y1 - y3) && x1 != x3 && y1 != y3) {
// 另外两个顶点
int count1 = pointCount.GetValueOrDefault((x1, y3), 0);
int count2 = pointCount.GetValueOrDefault((x3, y1), 0);
result += cnt * count1 * count2;
}
}
return result;
}
}
var DetectSquares = function() {
this.points = new Map();
};
DetectSquares.prototype.add = function(point) {
const key = point[0] + ',' + point[1];
this.points.set(key, (this.points.get(key) || 0) + 1);
};
DetectSquares.prototype.count = function(point) {
const [x, y] = point;
let count = 0;
for (const [key, freq] of this.points) {
const [px, py] = key.split(',').map(Number);
if (px === x || py === y) continue;
const side = Math.abs(px - x);
if (side !== Math.abs(py - y)) continue;
const key1 = x + ',' + py;
const key2 = px + ',' + y;
const freq1 = this.points.get(key1) || 0;
const freq2 = this.points.get(key2) || 0;
count += freq * freq1 * freq2;
}
return count;
};
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| add | O(1) | O(1) |
| count | O(n) | O(1) |
其中 n 是不同点的数量。在最坏情况下，n 可能达到坐标范围的上限，但实际受到调用次数限制。