[leetcode]: 447. Number of Boomerangs

灰太狼 2022-06-15 07:58 143阅读 0赞

# 1.题目 #

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\] (inclusive).

boomerangs定义为一个三个点组成的元组\[i,j,k\]，其中dist\[i,j\]=dist\[i,k\]，强调顺序。  
给出一组无重复的点，找出其中可以组成boomerangs的对数。  
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.分析 #

1）因为boomerangs强调顺序，所以每次以一个定点为i，然后求i与其他点之间的距离。  
2）求boomerangs的数量。假设求得的距离中有x个点与i点的距离相同，这x个点可以组成的boomerangs数量为  
![这里写图片描述][SouthEast]

# 3.代码 #

class Solution {
    public:
        int distance(pair<int, int> x, pair<int, int> y) {
            return (x.first - y.first)*(x.first - y.first) + (x.second - y.second)*(x.second - y.second);
        }
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int n = points.size();
            int counts = 0;
            for (int i = 0; i < n; i++) {
                unordered_map<int, int> dist;
                for (int j = 0; j < n; j++) {
                    if (i == j)
                        continue;
                    ++dist[distance(points[i], points[j])];
                }
                for (auto p : dist) {
                    if (p.second > 1)
                        counts += p.second*(p.second - 1);
                }
            }
            return counts;
        }
    };

[SouthEast]: /images/20220615/9202cfaa1eca4668ae2891ef59202dcf.png