Facebook面试题 | 回旋镖的数量

正文

请到「今天看啥」查看全文

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

请到「今天看啥」查看全文