0447. Number of Boomerangs ========================== 题目信息 -------- :题号: 0447 :难度: Medium :主题: 平面点、相等距离、有序三元组、数量统计 :原题: `LeetCode 0447 `_ :重点: 三个下标必须互不相同、以第一个点为中心、后两个点顺序不同算不同答案、比较欧氏距离 题目重述 -------- 给定平面上互不相同的点数组 ``points``。回旋镖定义为有序三元组 ``(i, j, k)``,其中三个下标互不相同,并且点 ``i`` 到点 ``j`` 的欧氏距离等于点 ``i`` 到点 ``k`` 的距离。返回所有回旋镖的数量。 ``points.length`` 位于 ``[1, 500]``,坐标位于 ``[-10^4, 10^4]``。三元组是有序的,所以固定中心 ``i`` 后,交换 ``j`` 和 ``k`` 会得到另一个答案。函数只返回数量,不需要列出三元组。 自建示例 -------- 三个共线且等距的点: .. code-block:: text 输入:points = [[-1,0], [0,0], [1,0]] 输出:2 解释:以 [0,0] 为中心时,两侧点距离都为 1;两个有序三元组分别交换左右点的顺序,因此计数为 2。 没有等距点对: .. code-block:: text 输入:points = [[0,0], [1,0], [0,2]] 输出:0 解释:对任何一个中心点,另外两点到它的距离都不相等。 固定中心统计等距点对 -------------------- 枚举中心点 ``i``,计算所有其他点到它的平方距离。若某个距离已经出现 ``c`` 次,新遇到的同距离点可以和此前的 ``c`` 个点组成 ``c`` 个有序选择;由于新点可以放在有序三元组的第二或第三个位置,这一轮贡献 ``2c``。 使用平方距离即可避免浮点数开方和精度问题。每个中心都重新建立频次表,处理完一个中心后清空其局部统计,避免把不同中心的距离混在一起。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int numberOfBoomerangs(std::vector>& points) { int answer = 0; for (int i = 0; i < static_cast(points.size()); ++i) { std::unordered_map frequency; for (int j = 0; j < static_cast(points.size()); ++j) { if (i == j) continue; long long dx = points[i][0] - points[j][0]; long long dy = points[i][1] - points[j][1]; long long distance = dx * dx + dy * dy; answer += 2 * frequency[distance]; ++frequency[distance]; } } return answer; } }; 代码分析 -------- 对固定中心,频次为 ``c`` 的距离最终会贡献 ``c(c-1)`` 个有序点对;在线累加 ``2c`` 正好实现同样的组合数,并区分交换后的两种顺序。每个中心检查其余所有点一次,时间复杂度为 ``O(n^2)``,单个频次表占用 ``O(n)`` 额外空间。