LeetCode447 Number of Boomerangs

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between iand j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

样例

1
2
3
4
5
6
7
8
Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

思路

统计有多少个$(i, j, k)$点对满足 $dis(i, j) = dis(i, k)$

固定一个点, 用map维护该点与其他点的距离。则每种距离对答案的贡献为$A^{2}_{n}$,$n$为该距离的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int dis(pair<int, int>& p1, pair<int, int>& p2) {
return (p1.first - p2.first) * (p1.first - p2.first) +
(p1.second - p2.second) * (p1.second - p2.second);
}
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int n = points.size(), ans = 0;
unordered_map<int, int> hs(n);
for (int i = 0; i < n; ++i) {
hs.clear();
for (int j = 0; j < n; ++j) hs[dis(points[i], points[j])]++;
for (auto& x: hs) ans += x.second * (x.second - 1);
}
return ans;
}
};
分享到 评论