每天一算： Number of Boomerangs

五分钟学算法

发布于 2018-11-20 15:41:59

5680

发布于 2018-11-20 15:41:59

leetcode上第447号问题：Number of Boomerangs

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 > i 和 k 之间的距离相等（需要考虑元组的顺序）。找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。示例: 输入: [[0,0],[1,0],[2,0]] 输出: 2 解释: 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

思路

n最大为500，可以使用时间复杂度为 O(n^2)的算法。

遍历所有的点，让每个点作为一个锚点
然后再遍历其他的点，统计和锚点距离相等的点有多少个
然后分别带入n(n-1)计算结果并累加到res中

Tips：

Tip1

如果有一个点a，还有两个点b和c，如果ab和ac之间的距离相等，那么就有两种排列方法abc和acb；
如果有三个点b，c，d都分别和a之间的距离相等，那么有六种排列方法，abc, acb, acd, adc, abd, adb；
如果有n个点和点a距离相等，那么排列方式为n(n-1)。

Tip2

计算距离时不进行开根运算, 以保证精度；
只有当n大于等于2时，res值才会真正增加，因为当n=1时，增加量为1*(1-1)=0。

动画演示

代码

 1// 447. Number of Boomerangs
 2// https://leetcode.com/problems/number-of-boomerangs/description/
 3// 时间复杂度: O(n^2)
 4// 空间复杂度: O(n)
 5class Solution {
 6public:
 7    int numberOfBoomerangs(vector<pair<int, int>>& points) {
 8
 9        int res = 0;
10        for( int i = 0 ; i < points.size() ; i ++ ){
11
12            // record中存储 点i 到所有其他点的距离出现的频次
13            unordered_map<int, int> record;
14            for(int j = 0 ; j < points.size() ; j ++){
15                if(j != i){
16                    // 计算距离时不进行开根运算, 以保证精度
17                    record[dis(points[i], points[j])] += 1;
18                }
19            }
20
21            for(unordered_map<int, int>::iterator iter = record.begin() ; iter != record.end() ; iter ++){
22                res += (iter->second) * (iter->second - 1);
23            }
24        }
25        return res;
26    }
27
28private:
29    int dis(const pair<int,int> &pa, const pair<int,int> &pb){
30        return (pa.first - pb.first) * (pa.first - pb.first) +
31               (pa.second - pb.second) * (pa.second - pb.second);
32    }
33};