问题描述
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]]
补充说明：
这个题目的要求大概是这个样子的：给定一个包含点坐标的list，最大长度为500，找到这个list中所有符合Boomerangs(回旋镖)规则的点的集合。这个单词我也没理解明白，但是根据提供的例子大概可以明白，意思就是生成的这个集合包含三个点i、j、k，点i到点j的距离等于点i到点k的距离。结果输出为给定这个列表中，满足这个条件的点集合的个数。
方案分析
- 看到这个题目，笔者第一反应就是想到了两点间的距离公式
pow(y2-y1, 2) + pow(x2-x1, 2)，毕竟初中数学。 - 知道如何判定了，就该想如何选点了，这里有个问题就是要选择三个点，自然而然想到了循环遍历，出于小聪明，笔者用python的情况下想到了
itertools中的一个函数permutations，这个函数能从一个可迭代的类型对象中选择指定个数元素，生成tuple集合。是不是很机智。可是这是噩梦的开始，先上代码。
python实现
class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
nums = 0
import itertools
for point_tuple in itertools.permutations(points, 3):
print point_tuple
if pow((point_tuple[1][1] - point_tuple[0][1]),2)\
+ pow((point_tuple[1][0] - point_tuple[0][0]),2)\
== pow((point_tuple[2][1] - point_tuple[0][1]),2)\
+ pow((point_tuple[2][0] - point_tuple[0][0]),2):
nums += 1
return nums
方案分析2
1.上面那个无外乎是在遍历所有情况，引用了高级函数一样不会避免枚举时间过长的问题，所以，上面方法不可行，原理上能讲明白，实际时间复杂度太高。
- ok，换个思路，使用hashmap，把里面所有的两点之间的距离计算一下，放到hashmap中，然后根据满足这个距离里面的点进行组合。这样就满足要求了。
- 讲解一下最后的那个
res += pDict[p] * (pDict[p] - 1)，这句话的意思是就是，当你发现两个点的距离为L时候，凡是满足L距离的点都存在了这个L为key的dict中，此时，你只需要从中任取3点，就能构成这个条件，因此，这样的组合有p×（p-1）对。
python实现2
class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
if len(points) < 3:
return 0
res = 0
for i in range(len(points)):
pDict = {}
for j in range(len(points)):
if j == i:
continue
dis = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2)
key = str(dis)
if key in pDict:
pDict[key] += 1
else:
pDict[key] = 1
for p in pDict:
if pDict[p] > 1:
res += pDict[p] * (pDict[p] - 1)
return res
