桂林视频网站制作,在线网页制作系统小彬,wordpress 搜索排除,上海搬家公司收费价目表2021题目来源
力扣447回旋镖的数量
题目描述
给定平面上 n 对 互不相同 的点 points #xff0c;其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 #xff0c;其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等#xff08;需要考虑元组的吮吸#xff09;…题目来源
力扣447回旋镖的数量
题目描述
给定平面上 n 对 互不相同 的点 points 其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等需要考虑元组的吮吸。
返回平面上所有回旋镖的数量。
示例
示例 1 输入points [[0,0],[1,0],[2,0]] 输出2 解释两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]] 示例 2 输入points [[1,1],[2,2],[3,3]] 输出2 示例 3 输入points [[1,1]] 输出0 提示 n points.length1 n 500points[i].length 2-10^4 xi, yi 10^4所有点都 互不相同 思路分析
回旋镖是由(i, j, k)三个点组成的三元组表示的我们可以取回旋镖的中心点 j 来表示这个回旋镖i 和 j 之间的距离与 j 与 k 之间的距离相等所以我们可以使用 key 为距离value 为与中心点距离为 key 值的数量的哈希表来保存距离及点个数。因为需要考虑顺序所以(i, j, k)与(k, j, i)是两个回旋镖我们可以使用组合公式来计算 value 个点中取两个有多少中方式value * (value - 1)。
p.s. 代码中的三元组为(j1, i, j2)
代码实现
java实现
public class Solution {public int numberOfBoomerangs(int[][] points) {int count 0;// 记录点到中心的距离及这个距离上点的数量MapInteger, Integer map new HashMap();// 回旋镖中心点for (int i 0; i points.length; i) {map.clear();// 保存距离及数量for (int j 0; j points.length; j) {if (i j) {continue;}int distance (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) ((points[i][1] - points[j][1])) * (points[i][1] - points[j][1]);map.put(distance, map.getOrDefault(distance, 0) 1);}// 使用组合公式计算回旋镖数量for (Integer distance : map.keySet()) {Integer num map.get(distance);count num * (num - 1);}}return count;}
}c实现
class Solution {
public:int numberOfBoomerangs(vectorvectorint points) {int count 0;// 到中心点的距离以及这个距离上点的数量mapint,int distanceCountMap;// i表示中心点for (int i 0; i points.size(); i) {distanceCountMap.clear();// 计算点的数量for (int j 0; j points.size(); j) {if (i j) {continue;}int distance (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) ((points[i][1] - points[j][1])) * (points[i][1] - points[j][1]);distanceCountMap[distance] distanceCountMap[distance] 1;}// 使用组合公式计算回旋镖数量for (auto iterator : distanceCountMap) {int num iterator.second;count num * (num - 1);}}return count;}
};
