问答

当前位置

Facebook面试题 | 回旋镖的数量

  • Ta: 张ms助教

题目描述

给出二维平面中的不同的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]]

解题思路分析

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)。

参考程序

面试官角度分析

这道题考察哈希表的应用,是中等偏简单的题目,给出O(N^2)的解法可达到hire。

lintcode相关问题

4sum

九章官网参考代码链接

Number Of Boomerangs 参考代码

0 个回复

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1