0447. 回旋镖的数量

0447. 回旋镖的数量 #

  • 标签:哈希表、数学
  • 难度:中等

题目大意 #

给定平面上点坐标的数组 points,其中 $points[i] = [x_i, y_i]$。判断 points 中是否存在三个点 i,j,k,满足 i 和 j 之间的距离等于 i 和 k 之间的距离,即 $dist[i, j] = dist[i, k]$。找出满足上述关系的答案数量。

解题思路 #

使用哈希表记录每两个点之间的距离。然后使用两重循环遍历坐标数组,对于每两个点 i、点 j,计算两个点之间的距离,并将距离存进哈希表中。再从哈希表中选取距离相同的关系中依次选出两个,作为三个点之间的距离关系 $dist[i, j] =dist[i, k]$,因为还需考虑顺序,所以共有 $value * (value-1)$ 种情况。累加到答案中。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for point_i in points:
            dis_dict = dict()
            for point_j in points:
                if point_i != point_j:
                    dx = point_i[0] - point_j[0]
                    dy = point_i[1] - point_j[1]
                    dis = dx * dx + dy * dy
                    if dis in dis_dict:
                        dis_dict[dis] += 1
                    else:
                        dis_dict[dis] = 1
            for value in dis_dict.values():
                ans += value*(value-1)
        return ans
本站总访问量  次  |  您是本站第  位访问者