447.Number of Boomerangs
447.Number of Boomerangs
难度:Easy
给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。
找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。
1
示例:
2
3
输入:
4
[[0,0],[1,0],[2,0]]
5
6
输出:
7
2
8
9
解释:
10
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
Copied!
建立一个表示距离关系的矩阵,然后统计每行相同距离的点。
1
class Solution {
2
public:
3
int numberOfBoomerangs(vector<vector<int>>& points) {
4
int N=points.size();
5
vector<vector<int>> distance(N, vector<int>(N,0));
6
for(int i=0;i<N;i++)
7
for(int j=i+1;j<N;j++)
8
{
9
distance[j][i]=distance[i][j]=pow((points[i][0]-points[j][0]),2)+pow((points[i][1]-points[j][1]),2);
10
//cout<< distance[i][j]<<endl;
11
}
12
int sum=0;
13
for(int i=0;i<N;i++)
14
{
15
unordered_map<int,int>tmp;
16
for(int j=0;j<N;j++)
17
{
18
if(tmp.count(distance[i][j]))
19
tmp[distance[i][j]]++ ;
20
else
21
tmp[distance[i][j]]=1;
22
}
23
for(auto iter=tmp.begin();iter!= tmp.end();iter++)
24
if(iter->second >1)
25
sum+=(iter->second)*(iter->second -1);
26
}
27
return sum;
28
}
29
};
Copied!
Copy link