Leetcode 447. 回旋镖的数量

题目描述

给定平面上 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
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容