|
1
2
3
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).
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的距离相等。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
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
