Problem
Solution
Analysis
Python implementation
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 implementation
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; } }
|
Time complexity
O(n^2).
Space complexity
O(n).
Link
447. Number of Boomerangs
(中文版) 算法笔记: 力扣#447 回旋镖的数量
近期评论