## “回形镖”的个数 Number of Boomerangs 原

叶枫啦啦

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]]```

【解析】

①点(x,y)与(x1,y1)之间的距离为(x1 - x) * (x1 - x) + (y1 - y) * (y1 - y)，将与点(x,y)距离相同的点保存在hashmap中，这样就找到了n个与与点(x,y)距离相同的点。那么在这n个点中任意选出两个点与点(x,y)构成三元组，有n*(n -1)种排列组合方式（与排列顺序有关）。

public class Solution {
public int numberOfBoomerangs(int[][] points) {
int count = 0;
for (int i = 0;i < points.length ;i ++ ) {//记录下(x1,y1)相对于点(x,y)
int x = points[i][0];
int y = points[i][1];
Map<Long,Integer> map = new HashMap<>();//键---距离，值---距离相同的点的个数，必须放在循环内
for (int j = 0;j < points.length ;j ++ ) {
int x1 = points[j][0];
int y1 = points[j][1];
long distance = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
map.put(distance,map.getOrDefault(distance,0) + 1);
}
for (Map.Entry<Long,Integer> entry : map.entrySet()) {//必须放在循环内计算
int val = entry.getValue();
count += val * (val - 1);//距离相同的点有n*(n-1)种排列组合方式
}
}
return count;
}
}

②直接统计可以进行的排列个数，耗时107ms。

public class Solution {
public int numberOfBoomerangs(int[][] points) {
int count = 0;
HashMap<Integer,Integer> map = new HashMap<>();
for(int[] p1 : points){//遍历节点
for(int[] p2 :points){
if(p1 == p2) continue;//同一个点则略过
int distance = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);//计算两点间的距离
int preCount = map.getOrDefault(distance,0);
count += 2 * preCount;//p1,p2两个位置可以颠倒
map.put(distance,preCount + 1);
}
map.clear();
}
return count;
}
}

### 叶枫啦啦

LeetCode算法题-Number of Boomerangs（Java实现）

01/15
0
0
Leetcode PHP题解--D103 447. Number of Boomerangs

D103 447. Number of Boomerangs 题目链接 447. Number of Boomerangs 题目分析 给定一个坐标数组，从中任意取3个坐标，使得从i到j的距离等于i到k的距离。且与不是同一个组合，需单独计算。 ...

skys215
07/14
13
0
leetcode题解(查找表问题)

2018/06/21
0
0

2016/06/22
9
0

2017/12/21
0
0

chro008
21分钟前
12
0
idea 2019.2免费激活码

Iverson58
29分钟前
7
0

a429011717
36分钟前
6
0
Qt编写自定义控件69-代码行数统计

55分钟前
12
0

5
0