GuilinDev
Lc0447
05 August 2008
*447 - Number of Boomerangs
原题概述
Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points 1
(i, j, k)
1
i
1
j
1
i
1
k
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:
1
2
3
4
5
6
7
8
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]]
题意和分析
定义了一种类似回旋镖形状的三元组结构，要求第一个点和第二个点之间的距离跟第一个点和第三个点之间的距离相等。现在给了n个点，找出回旋镖的个数。那么如果有一个点a，还有两个点b和c，如果ab和ac之间的距离相等，那么就有两种排列方法abc和acb；如果有三个点b，c，d都分别和a之间的距离相等，那么有六种排列方法，abc, acb, acd, adc, abd,adb，那么是怎么算出来的呢，很简单，如果有n个点和a距离相等，那么排列方式为n(n-1)，这属于最简单的排列组合问题了。如此就可以遍历所有点，让每个点都做一次点a，然后遍历其他所有点，统计和a距离相等的点有多少个，然后分别带入n(n-1)计算结果并累加到result中，只有当n大于等于2时，result值才会真正增加。
时间复杂度O(n^2)，空间复杂度O(n)。
如果定义一个这样的二维数组int a[3][4]={ {1,3,5,7},{9,11,13,15},{17,19,21,23} };则其在内存中的表示下面这样的。
在内存中二维数组是按照行主序进行存储的，从内存的角度上看，二维数组本质就是一个一维数组。如果把二维数组的每一行看成一个整体，即看成一个数组中的一个元素，那么整个二维数组就是一个一维数组。而二维数组的名字代表二维数组第0行的首地址(注意它是代表一行元素的首地址，而不是第0行第0列元素的首地址，虽然是相等的，但不能这么理解，所以在没有强制转换的情况下，二维数据要么通过行指针进行参数传递，要么通过二维指针进行参数传递)。
代码
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
class Solution {
public int numberOfBoomerangs(int[][] points) {
if (points == null || points.length == 0) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
int result = 0;
for (int i = 0; i < points.length; i++) {
for (int j = 0; j < points.length; j++) {
if (i == j) {//自己和自己不用比较
continue;
}
int distance = getDistance(points[i], points[j]);
map.put(distance, map.getOrDefault(distance, 0) + 1);//key是distance,value是距这个点相同distance的点的个数
}
for (int n : map.values()) {
result += n * (n - 1);//排列方式为n(n-1)
}
map.clear();//清空map，下一轮检查一个新的点
}
return result;
}
private int getDistance(int[] a, int[] b) {
int dx = a[0] - b[0];
int dy = a[1] - b[1];
return dx*dx + dy*dy;
}
}