每天一算: Number of Boomerangs
16lz
2021-01-22
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};
执行结果
更多相关文章
- 盘一盘机器学习中的那些距离
- PHP实例计算经纬坐标间的距离
- 同样的复杂度,为什么插入排序比冒泡排序更受欢迎?
- 数据结构--时间复杂度与空间复杂度
- jquery判断滚动条距离顶部的距离
- [LeetCode] 244. Shortest Word Distance II 最短单词距离 II
- 根据两点经纬度计算距离和角度——java实现
- java 百度地图判断两点距离1