Python 中的回旋镖数量

pythonserver side programmingprogramming更新于 2026/1/27 18:20:17

假设平面上有 n 个点，它们都是成对不同的。现在"回旋镖"是一个点元组，如 (i, j, k)，其中 i 和 j 之间的距离与 i 和 k 之间的距离相同。我们必须找到回旋镖的数量。

因此，如果输入为 [[0,0],[1,0],[2,0]]，则输出将为 2，因为两个回旋镖分别为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]。

为了解决这个问题，我们将遵循以下步骤 −

counter_of_boomerangs := 0
对于 points 数组中的每个 point_1，执行
- x1, y1 = point_1
- 定义一个名为 distance_count_dict 的映射
- 对于 points 数组中的每个 point_2，执行
  - x2, y2 = point_2
  - diff_x := x2 - x1
  - diff_y := y2 - y1
  - dist := diff_x^2 + diff_y^2
  - distance_count_dict[ dist ] := distance_count_dict[ dist ] + 1
- for each d in distance_count_dict −
  - n := distance_count_dict[d]
  - counter_of_boomerangs := counter_of_boomerangs + n * (n - 1)
返回 counter_of_boomerangs

示例

让我们看看下面的实现以便更好地理解 −

from collections import defaultdict
class Solution:
   def numberOfBoomerangs(self, points):
      counter_of_boomerangs = 0
      for point_1 in points:
         x1, y1 = point_1
         distance_count_dict = defaultdict( int )
         for point_2 in points:
            x2, y2 = point_2
            diff_x = x2-x1
            diff_y = y2-y1
            dist = diff_x ** 2 + diff_y ** 2
            distance_count_dict[ dist ] += 1
         for d in distance_count_dict:
            n = distance_count_dict[d]
            counter_of_boomerangs += n * (n-1)
      return counter_of_boomerangs

ob = Solution()
print(ob.numberOfBoomerangs([[0,0],[1,0],[2,0]]))