天猫网站企业网站专业性诊断分析,公众号绑定网站,做招聘信息的网站,江苏建设人才官方网站一、题目
1、题目描述 给定平面上 n 对 互不相同 的点 points #xff0c;其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 #xff0c;其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等#xff08;需要考虑元组的顺序#xff09;。 返回平面上所有回…一、题目
1、题目描述 给定平面上 n 对 互不相同 的点 points 其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等需要考虑元组的顺序。 返回平面上所有回旋镖的数量。 2、接口描述
class Solution {
public:int numberOfBoomerangs(vectorvectorint points) {}
}; 3、原题链接
447. 回旋镖的数量 二、解题报告
1、思路分析
可见符合条件的三个点构成了一个等腰三角形那么我们固定一个点去计算和其它所有点的距离对于距离为k的点的数目由m个那么就加上A(2 , m)固定每个点然后计算一次即可
2、复杂度 时间复杂度O(n^2) 空间复杂度O(n) 3、代码详解
class Solution {
public:int numberOfBoomerangs(vectorvectorint points) {int ret 0;for(auto x : points){unordered_mapint , int hash;for(auto y : points)hash[(x[0] - y[0]) * (x[0] - y[0]) (x[1] - y[1]) * (x[1] - y[1])];for(auto [_ , m] : hash)ret m * (m - 1);}return ret;}
};
