Number of Boomerangs

题目来源
给一堆点坐标,让你求出一堆的三个点{a, b, c}集合,其中ab距离和ac距离一样。
我只能想到暴力的方法,先把每一个点都哈希一下存起来,然后再遍历,取两点,判断对应的第三点是否存在。
抄的代码,代码如下:

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int res = 0;
        int n = points.size();
        for (int i=0; i<n; i++) {
            unordered_map<double, int> map;
            for (int j=0; j<n; j++) {
                int deltaX = points[i].first - points[j].first;
                int deltaY = points[i].second - points[j].second;
                res += 2 * map[hypot(deltaX, deltaY)]++;
            }
        }
        return res;
    }
};

重点在于计算res的过程,2+4+6+8+...+2n = n(n+1)
map先申请好,这样子快了一些:

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int res = 0;
        int n = points.size();
        for (int i=0; i<n; i++) {
            unordered_map<double, int> map(n-1);
            for (int j=0; j<n; j++) {
                if (i == j)
                    continue;
                int deltaX = points[i].first - points[j].first;
                int deltaY = points[i].second - points[j].second;
                res += 2 * map[deltaX*deltaX+deltaY*deltaY]++;
            }
        }
        return res;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容