题目描述
给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。
找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。
示例 1:
输入: [[0,0],[1,0],[2,0]]
输出: 2
解释: 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
解法
根据题意可知,数组中存在 n
个不同的点,以数组中某一个点为中心,若存在两个点到该中心点的距离相同,则存在两个回旋镖(因为考虑了回旋镖的点顺序)。
所以不妨求出数组中每个点到中心点的距离,若存在 x
个点到该中心点的距离相同,则存在 x*(x-1)
个回旋镖。
class Solution:
def numberOfBoomerangs(self, points: List[List[int]]) -> int:
ret=0
d=dict()
for x,y in points:
for x1,y1 in points:
dis=(x1-x)**2+(y1-y)**2
d[dis]=d.get(dis,0)+1
for n in d.values():
ret+=n*(n-1)
d.clear()
return ret