447. Number of Boomerangs
1 static int wing=[]() 2 { 3 std::ios::sync_with_stdio(false); 4 cin.tie(NULL); 5 return 0; 6 }(); 7 8 class Solution 9 { 10 public: 11 int numberOfBoomerangs(vector<pair<int, int>>& points) 12 { 13 int res=0; 14 int szp=points.size(); 15 int dis[szp]; 16 for(int i=0;i<szp;i++) 17 { 18 for(int j=0;j<szp;j++) 19 { 20 int dx=points[i].first-points[j].first; 21 int dy=points[i].second-points[j].second; 22 dis[j]=dx*dx+dy*dy; 23 } 24 sort(dis,dis+szp); 25 int count=1; 26 for(int k=1;k<szp;k++) 27 { 28 if(dis[k]==dis[k-1]) 29 count++; 30 else 31 { 32 res+=count*(count-1); 33 count=1; 34 } 35 } 36 res+=count*(count-1); 37 } 38 return res; 39 } 40 };
本质还是暴力解法,双层循环
但是在容器上的选择很重要,用数组比vector快,用vector比用map快
以上方法为运行速度最快的一种,用的数组。
优质内容筛选与推荐>>