447 Number of Boomerangs

447. Number of Boomerangs

1. Question

Givennpoints in the plane that are all pairwise distinct, a "boomerang" is a tuple of points(i, j, k)such that the distance betweeniandjequals the distance betweeniandk(the order of the tuple matters).

Find the number of boomerangs. You may assume thatnwill be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input: [[0,0],[1,0],[2,0]]

Output: 2

Explanation:

The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

2. Implementation

思路: (1) 对每个point A，我们都找出它和其他点所形成的距离

(2) 将这些距离存入一个hashmap中，key是距离的值，value是和point A构成这个距离值得点的个数

(3) 接下来如果point A对应的是boomerang的i, 那么我们接下来要求(j, k)的总排列. 遍历hashmap，对于每个key对应的value，根据排列公式 n!/ (n - 2)! = n(n - 1), 能形成boomberangs的个数等于 value * (value - 1)

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                int distance = getDistance(points[i], points[j]);

                map.put(distance, map.getOrDefault(distance, 0) + 1);
            }

            for (Integer value : map.values()) {
                res += value * (value - 1);
            }
            map.clear();
        }
        return res;
    }

    public int getDistance(int[] p1, int[] p2) {
        int dx = p1[0] - p2[0];
        int dy = p1[1] - p2[1];
        return dx * dx + dy * dy;
    }
}

3. Time & Space Complexity

时间复杂度O(n^2), 空间复杂度O(n)