leetcode 447. Number of Boomerangs 中位数Map统计 + 公式计算

分手后的思念是犯贱 2022-06-04 08:39 129阅读 0赞

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).

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

题意很简单，就是寻找两个点的中位数，直接循环计算即可

**这道题需要注意的地方就是数据溢出问题**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& p) 
        {
            int count = 0;
            for (int i = 0; i < p.size(); i++)
            {
                map<long long, int> mmp;
                for (int j = 0; j < p.size(); j++)
                {
                    if (i == j)
                        continue;
                    long long len = (p[i].first - p[j].first)*(p[i].first - p[j].first) + (p[i].second - p[j].second)*(p[i].second - p[j].second);
                    if (mmp.find(len) == mmp.end())
                        mmp[len] = 1;
                    else
                        mmp[len] += 1;
                }
                for (pair<long long, int> pp : mmp)
                {
                    if (pp.second > 1)
                        count += pp.second*(pp.second - 1);
                }
            }
            return count;
        }
    };