问题描述
解法
分析
Python 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
class : def numberOfBoomerangs(self, points): """ :type points: List[List[int]] :rtype: int """ ans = 0 for x1, y1 in points: counter = {} for x2, y2 in points: if x1 != x2 or y1 != y2: distance = (x1-x2)**2 + (y1-y2)**2 counter[distance] = counter.get(distance, 0)+1 ans += sum(n*(n-1) for n in counter.values()) return ans
|
Java 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
class { public int numberOfBoomerangs(int[][] points) { int ans = 0; for(int[] point1 : points){ Map<Double, Integer> counter = new HashMap<>(); for(int[] point2 : points){ if(point1[0]!=point2[0] || point1[1]!=point2[1]){ double distance = Math.pow(point1[0]-point2[0],2)+Math.pow(point1[1]-point2[1],2); counter.put(distance, counter.getOrDefault(distance, 0)+1); } } for(int n : counter.values()){ ans += n*(n-1); } } return ans; } }
|
时间复杂度
O(n^2).
空间复杂度
O(n).
链接
447. Number of Boomerangs
447. 回旋镖的数量
(English version) Algorithm Notes: Leetcode#447 Number of Boomerangs
近期评论