作者 | 施助教+本助教 
编辑 | Ivy Xu
专栏 | 九章算法
1
题目描述
给出二维平面中的不同的N个点，找出回旋镖三元组的数量。
一个三元组(A,B,C)，如果满足点A到点B的距离等于点A到点C的距离，则被称为回旋镖。
同样三个点，不同顺序的三元组算不同的三元组。
N<=500，所有点的坐标值为整数且都在[-10000,10000]中。
样例
输入: [[0,0],[1,0],[2,0]]

输出: 2

说明: 共有两个回旋镖，分别为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
2
解题思路分析
a. 一个简单的方法是枚举所有三元组，判断是否满足条件并计数，时间复杂度为O(N^3)。
b. 对于一个点A来说，如果有k个点到A的距离相等，那么就可以形成k*(k-1)个回旋镖（在k个点中任意选取两个不同的点均可以和A形成回旋镖，且不同的顺序算不同的方案）。
计算所有其他点到A点的距离，统计离A点有某个相同距离d的点有几个，最后将所有个数代入k*(k-1)并相加，就得到了所有以A点为三元组中第一个点的回旋镖个数。
枚举所有点用相同的方式计算出以该点为第一个点的回旋镖数量并相加，即可得到答案。
c. 如何存储并统计离一个点距离为d的个数呢？
首先，如果直接按距离去统计，由于距离为实数，判断相等时应考虑精度问题，但如果直接考虑距离的平方，则对于给出的坐标值的大小（[-10000,10000]），其距离的平方仍在32位整数int范围内。
尽管如此，距离的平方的取值范围仍然很大（[0,800000000]），但对于一个点A来说，剩余的N-1个点到这个点的距离只有N-1个。
故可以用HashMap存储键值对（到点A的距离平方，对应距离的点的个数）。
d. 综上所述，枚举点A并枚举剩下的点时间复杂度为O(N^2)，每次存取HashMap的时间复杂度为O(1)，总的时间复杂度为O(N^2)。
3
参考程序
4
面试官角度分析
这道题考察哈希表的应用，是中等偏简单的题目，给出O(N^2)的解法可达到hire。
5
lintcode相关问题
http://www.lintcode.com/zh-cn/problem/4sum/
6
九章官网参考代码链接
http://www.jiuzhang.com/solution/number-of-boomerangs/
更多精彩内容
  • 回复“简历”，查看简历撰写指南，获取“简历模板”
  • 回复“冷冻期”，查看北美各大IT企业冷冻期信息和注意事项
  • 回复“Career”, 查看Caireer Fair 攻略 check list
  • 回复“薪资”，查看北美各大IT企业New Grades Engineer 薪资水平；
  • 回复“项目”，查看7-14天可以搞定的小项目推荐
  • 回复“评分”，查看系统设计评分指南
  • 回复“behavior”，查看behavior interview指南
  • 回复“晋升”，查看Engineer晋升机制 
《算法面试高频题班》| 本周免费试听
Google/Facebook等大公司高频题各有什么特点？
通过四道题目举例详解Google/Facebook/Linkedin/Amazon各公司面试特点
剖析各大It企业面试算法类型分布情况
2017年秋招备战进行时
赢在起跑线！
报名登陆官网 www.jiuzhang.com
或点击文末“阅读原文”
继续阅读
阅读原文