首页 > itarticle > 算法笔记: 力扣#447 回旋镖的数量

算法笔记: 力扣#447 回旋镖的数量

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

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 实现

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