【Leetcode】 447. 回旋镖的数量

发布时间:2024年01月09日

文章目录

题目

447. 回旋镖的数量
在这里插入图片描述

思路

问题要求计算平面上所有回旋镖的数量,即找到满足题设条件的点组合 (i, j, k)。回旋镖的定义是指有两个相同的距离,分别从点 i 到 j 和点 i 到 k。具体思路是:

遍历每个点,以其为中心,计算它与其他点的距离,并将这些距离存储下来。

对于每个点 i,遍历其余所有点 j,计算点 i 到点 j 的距离,并将距离作为键,出现的频次作为值,存储在哈希表中。

针对每个点 i,遍历哈希表中记录的距离和频次,如果某个距离有至少两个点与点 i 的距离相等,则可以形成回旋镖。对于每个满足条件的距离 d,假设有 m 个点与点 i 的距离等于 d,则回旋镖的数量为 m * (m - 1),因为对于第一个点有 m 种选择,对于第二个点有 m - 1 种选择。

统计所有点的回旋镖数量,并将其累加,最后得到所有回旋镖的总数。

代码

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        vector<unordered_map<int,int>>mapp(n);
        for(int i = 0;i < n; ++i){
            for(int j = i + 1; j < n; ++j){
                auto t = pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2);
                res -= mapp[i][t] * (mapp[i][t] - 1);
                res -= mapp[j][t] * (mapp[j][t] - 1);
                mapp[i][t]++;
                mapp[j][t]++;
                res += mapp[i][t] * (mapp[i][t] - 1);
                res += mapp[j][t] * (mapp[j][t] - 1);
            }
        }
        return res;
    }
};
文章来源:https://blog.csdn.net/m0_67724631/article/details/135469255
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。