LeetCode 447. 回旋镖的数量,枚举+哈哈希

2024-01-08 10:21:04

一、题目

1、题目描述

给定平面上?n?对?互不相同?的点?points?,其中?points[i] = [xi, yi]?。回旋镖?是由点?(i, j, k)?表示的元组 ,其中?i?和?j?之间的距离和?i?和?k?之间的欧式距离相等(需要考虑元组的顺序)。

返回平面上所有回旋镖的数量。

2、接口描述

?
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {

    }
};

3、原题链接

447. 回旋镖的数量


二、解题报告

1、思路分析

可见符合条件的三个点构成了一个等腰三角形,那么我们固定一个点,去计算和其它所有点的距离,对于距离为k的点的数目由m个,那么就加上A(2 , m),固定每个点然后计算一次即可

2、复杂度

时间复杂度:O(n^2) 空间复杂度:O(n)

3、代码详解

?
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
       int ret = 0;
       for(auto& x : points)
       {
            unordered_map<int , 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;
    }
};

文章来源:https://blog.csdn.net/EQUINOX1/article/details/135448405
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。