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;
    }
};
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容