Skip to content

Latest commit

 

History

History
59 lines (42 loc) · 1.86 KB

447-number-of-boomerangs.md

File metadata and controls

59 lines (42 loc) · 1.86 KB

447. Number of Boomerangs - 回旋镖的数量

给定平面上 n 对不同的点,“回旋镖” 是由点表示的元组 (i, j, k) ,其中 i 和 j 之间的距离和 i 和 k 之间的距离相等(需要考虑元组的顺序)。

找到所有回旋镖的数量。你可以假设 n 最大为 500,所有点的坐标在闭区间 [-10000, 10000] 中。

示例:

输入:
[[0,0],[1,0],[2,0]]

输出:
2

解释:
两个回旋镖为 [[1,0],[0,0],[2,0]][[1,0],[2,0],[0,0]]

题目标签:Hash Table

题目链接:LeetCode / LeetCode中国

题解

Language Runtime Memory
python3 1720 ms N/A
class Solution:
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if len(points) < 3:
            return 0
        ds = {k: collections.defaultdict(int) for k in range(len(points))}
        for i in range(len(points)-1):
            for j in range(i+1, len(points)):
                d = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
                ds[i][d] += 1
                ds[j][d] += 1
        res = 0
        for point in ds.values():
            for c in point.values():
                if c > 1:
                    res += c * (c - 1)
        return res