LeetCode 447. 回旋镖的数量
题目描述
题意分析
从互不相同的平面点中，统计三个不同点组成的有序三元组
(i, j, k)，要求i到j的距离等于i到k的距离。i是中心，交换j、k后是另一个回旋镖。
解法：按距离分组计数
核心思路
[!blue]
先固定中心
i，问题就变成：从距离中心相同的一组点中，选出两个不同点并安排顺序。若这组有m个点，第一位有m种选择，第二位有m - 1种选择，贡献为m * (m - 1)。用哈希表按距离平方分组，平方距离相等就等价于距离相等，无需开方。代码在扫描时直接计数：当前点到来之前，同距离已有
c个点，它与每个旧点都能按两种顺序配对，所以新增2 * c，然后才将频次加一。每对点恰好在后扫描到的那个点到来时计入，不会重复或遗漏。每换一个中心就创建新的频次表。不同中心对应三元组的第一项不同，计数可以直接相加；扫描其他点时跳过中心自身，保证三个点互不相同。
解题步骤
- 枚举每个点
i作为中心，创建空频次表cnt。- 遍历所有
j != i的点，计算d2 = dx * dx + dy * dy。- 取出旧频次
c = cnt[d2]，将答案增加2 * c，再令cnt[d2] = c + 1。- 所有中心处理完后返回总答案。点不足三个时，自然不会形成有效配对。
代码实现
class Solution {
public int numberOfBoomerangs(int[][] points) {
int n = points.length;
int answer = 0;
for (int i = 0; i < n; i++) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int j = 0; j < n; j++) {
if (j == i) {
continue;
}
int dx = points[i][0] - points[j][0];
int dy = points[i][1] - points[j][1];
int d2 = dx * dx + dy * dy;
// 使用加入前的频次，每个同距离旧点贡献两种有序配对。
int same = cnt.getOrDefault(d2, 0);
answer += 2 * same;
cnt.put(d2, same + 1);
}
}
return answer;
}
}
func numberOfBoomerangs(points [][]int) int {
n := len(points)
answer := 0
for i := 0; i < n; i++ {
cnt := make(map[int]int)
for j := 0; j < n; j++ {
if j == i {
continue
}
dx := points[i][0] - points[j][0]
dy := points[i][1] - points[j][1]
d2 := dx*dx + dy*dy
// 使用加入前的频次，每个同距离旧点贡献两种有序配对。
answer += 2 * cnt[d2]
cnt[d2]++
}
}
return answer
}
复杂度分析
- 时间复杂度：期望 $O(n^2)$，其中
n为点数；每个中心扫描全部其他点，每次进行常数次哈希操作。- 空间复杂度：$O(n)$，只保存当前中心的距离计数。
关键点总结
[!green]
- 有序对需计入两个排列方向。
- 频次表随中心重建，不能跨中心累计。
- 贡献使用加入当前点之前的频次。
易错点总结
[!yellow]
- 使用组合数只计一次顺序：答案少一半。
- 只枚举下标比中心大的点：漏掉中心左侧下标的合法邻点。
- 更新频次后用新频次计算贡献：把当前点与自身配对。
- 不同中心共用未清空的表：混淆不同距离分布。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 149. 直线上最多的点数 | 困难 | 同样固定锚点再把其余点按特征分组，原题按方向分组，本题按距离平方分组。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！