数学：Leetcode447:回旋镖的数量

Bertha 。 2023-10-06 08:46 1阅读 0赞

## 数学：Leetcode447:回旋镖的数量 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]

#### 思路： ####

用哈希表记录每个点到其他点的线段长度

使用unordered\_map，键代表线段长度，值代表该线段长度出现的次数

对于每个点，若相同的线段长度出现了2次及以上，则存在回旋镖。设相同的线段长度出现次数为n，从n=1开始，每次新增一次出现次数，回旋镖的数量增加2\*（n-1），以下为证明：

当n增加1时，新增的回旋镖为：在（n-1）个点中选一个，与新增的点组合，由于这两个点在元组中的位置可以互换，新增的回旋镖总数即为 2\*（n-1）  
![在这里插入图片描述][20200514103517756.png]

#### 代码： ####

class Solution {
        
    public:
        int numberOfBoomerangs(vector<vector<int>>& points) {
        
            unordered_map<int,int> table;
            int i;
            int j;
            int distance=0;
            int count=0;
            for( i=0;i<points.size();i++ )
            {
           
                table.clear();
                for( j=0;j<points.size();j++ )
                {
        
                    if( j!=i )
                    {
        
                        distance=pow( points[j][0]-points[i][0],2 )+pow( points[j][1]-points[i][1],2 );
                        table[distance]++;
                        if( table[distance]>1 )
                            count+=2*( table[distance]-1 );
                    }
                }
            }
            return count;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200514102504378.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20200514103517756.png]: https://img-blog.csdnimg.cn/20200514103517756.png