LeetCode 447. Number of Boomerangs（回旋镖的数量）

题目描述

Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range -10000, 10000.

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]]

解法一

思路

这题换个说法就是，在二维坐标系下有若干个点，求满足x和y的距离与y和z的距离相等的三个点x、y和z的数目。

想要知道距离是否相等，那首先就要知道距离的值，这样就免不了要遍历了。即对于每个点y，遍历其他的点，并寻找不同的点x和z，满足x和y的距离与y和z的距离相等。怎么来统计距离相等的点的数目呢？这里有一个优化的方法，对于点y，遍历其他点时，我们只需要用一个Map来维护(距离, 点的个数)这样的键值对。遍历完成后再遍历这个Map，如果值为2，则代表有两个点满足要求，记录满足要求的(x, y, z)为2（因为题目要求考虑点的顺序，所以(x, y, z)和(z, y, z)都分别满足题目要求）；而如果值大于2，则代表有多个点满足要求，而且其中任意两个点的排列（考虑到顺序）都是符合题意的。这样就得到了以y为中心点的满足题目要求的情况数目，遍历完所有的点即得到最终结果。

Python

class Solution:
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        result = 0
        for point_a in points:
            distances = {}
            for point_b in points:
                distance = (point_a[0] - point_b[0]) ** 2 + (point_a[1] - point_b[1]) ** 2
                distances[distance] = distances.get(distance, 0) + 1
            result += sum(item * (item - 1) for item in distances.values())
        return result

Java

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int result = 0;
        for (int[] pointA : points) {
            Map<Integer, Integer> distances = new HashMap<>();
            for (int[] pointB : points) {
                int distance = (pointA[0] - pointB[0]) * (pointA[0] - pointB[0]) + (pointA[1] - pointB[1]) * (pointA[1] - pointB[1]);
                distances.put(distance, distances.getOrDefault(distance, 0) + 1);
            }
            for (int item : distances.values()) {
                result += item * (item - 1);
            }
        }
        return result;
    }
}

C++

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>> &points) {
        int result = 0;
        for (auto &pointA : points) {
            map<int, int> distances;
            for (auto &pointB : points) {
                int distance = (pointA.first - pointB.first) * (pointA.first - pointB.first) +
                               (pointA.second - pointB.second) * (pointA.second - pointB.second);
                distances[distance]++;
            }
            for (auto &item : distances) {
                result += item.second * (item.second - 1);
            }
        }
        return result;
    }
};