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 i and 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).
Example:
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]]
这道题开始我的第一想法是用回溯法,穷举出所有的三个点的排列,然后挑选出距离相等的组合,这样做结果超时了。
错误示范
class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int> >& points)
{
if(points.size()<3)
return 0;
vector<pair<int, int> >temp;
int num=0;
recursive(points,temp,0,num,0);
return num;
}
void recursive(vector<pair<int, int> >& points,vector<pair<int, int> >& temp,int count,int &num,int start)
{
if(count==3)
{
for(int j=0;j<3;j++)
cout<<temp[j].first<<' '<<temp[j].second<<'\t';
cout<<endl;
if(distance(temp[0],temp[1])==distance(temp[0],temp[2]))
num=num+2;
if(distance(temp[1],temp[0])==distance(temp[1],temp[2]))
num=num+2;
if(distance(temp[2],temp[0])==distance(temp[2],temp[1]))
num=num+2;
return;
}
for(int i=start;i<points.size();i++)
{
if(find(temp.begin(),temp.end(),points[i])!=temp.end())
continue;
temp.push_back(points[i]);
recursive(points,temp,count+1,num,i+1);
temp.pop_back();
}
}
int distance(pair<int, int> &a,pair<int, int> &b)
{
int x=(a.first-b.first)*(a.first-b.first);
int y=(a.second-b.second)*(a.second-b.second);
return x+y;
}
};
第二种方法:利用hash表,存储每一个点和其他点的距离,当相同距离的点个数超过2时,就可以组合三个点;时间复杂度为O(N^2)
class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int> >& points)
{
if(points.size()<3)
return 0;
int ret=0;
for(int i=0;i<points.size();i++)
{
unordered_map<int,int>hashmap;
for(int j=0;j<points.size();j++)
{
if(j==i)
continue;
int dis=distance(points[i],points[j]);
hashmap[dis]++;
}
for(auto it=hashmap.begin();it<hashmap.end();it++)
{
if(it->second>=2)
ret=ret+it->second*(it->second-1);
}
}
return ret;
}
int distance(pair<int, int> &a,pair<int, int> &b)
{
int x=(a.first-b.first)*(a.first-b.first);
int y=(a.second-b.second)*(a.second-b.second);
return x+y;
}
};