Leetcode 447. Number of Boomerangs JAVA语言-白红宇

                         
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).
Example:
Input:[[0,0],[1,0],[2,0]]Output:2Explanation:The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

题意：给出n个点的坐标，找到ijk三个点，使得i到j和k的距离相等。

                         
public
class
Solution { 
    
public
int
numberOfBoomerangs(
int
[][] points) { 
        
还有负数。。。。。hehe....坐标轴。。。。并不是只有x轴
        
// int length=points.length;
        
// int m;
        
// int count=0;
        
// for(int i=0;i<length;i++){ 
        
//     m=1;
        
//     while(i+m<=length-1 && i-m>=0){ 
        
//         if(points[i][0]-points[i-m][0]==points[i+m][0]-points[i][0]){ 
        
//             count=count+2;
        
//         }
        
//         m++;
        
//     }
        
// }
        
// // System.out.println(length);
        
// return count;
        
//http://blog.csdn.net/MebiuW/article/details/53096120
        
//  int length=points.length;
        
//  int count=0;
        
//  for(int i=0;i<length;i++){ 
        
//      HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        
//      for(int j=0;j<length;j++){ 
        
//          int dist=(points[i][0]-points[j][0])*(points[i][0]-points[j][0])+(points[i][1]-points[j][1])*(points[i][1]-points[j][1]);
        
//          if(!map.containsKey(dist)){ 
        
//              map.put(dist,0);
        
//          }
        
//          count+=map.get(dist)*2;
        
//          map.put(dist,map.get(dist)+1);
        
//      }
        
//  }
        
//  return count;
        
//也是遍历，求与其距离相同的点的个数，最后就是个数（个数-1）
        
///感觉还是这个好理解一些~
        
int
length=points.length;
        
int
count=
0
;
        
int
dist=
0
;
        
for
(
int
i=
0
;i<length;i++){ 
            
HashMap<Integer,Integer> map=
new
HashMap<Integer,Integer>();
            
for
(
int
j=
0
;j<length;j++){ 
                
if
(i==j){ 
                    
continue
;
                
}
else
{ 
                    
dist=(points[i][
0
]-points[j][
0
])*(points[i][
0
]-points[j][
0
])+(points[i][
1
]-points[j][
1
])*(points[i][
1
]-points[j][
1
]);
                    
if
(!map.containsKey(dist)){ 
                        
map.put(dist,
1
);
                    
}
else
{ 
                        
map.put(dist,map.get(dist)+
1
);    
                    
}
                
}
                
            
}
        
Iterator it = map.keySet().iterator();  
        
while
(it.hasNext()) {  
            
int
key = (
int
)it.next();  
            
count+=map.get(key)*(map.get(key)-
1
);
            
// System.out.println("value:" + hashMap.get(key));  
            
} 
        
}
        
return
count;
    
}
}
        
      

PS：第一次以为只有x轴正半轴，然后才发现其实是x,y轴4个空间。

最后的思想是遍历所有点，找到所有点距其距离相等的点的个数n，那么就有n(n-1)个，不断累加即可。

本文转自努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1891285