首页 > 代码库 > [LeetCode] Number of Boomerangs
[LeetCode] Number of Boomerangs
Given n points in the plane that are all pairwise distinct, a "boomerang" is a tuple of points (i, j, k)
such that the distance between i
and j
equals the distance between i
and k
(the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).
Example:
Input: [[0,0],[1,0],[2,0]] Output: 2 Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
给定一个坐标数组,计算在这组坐标中,某一点到另外任意两个点直接距离相等的组合。假设固定1个点,满足条件的点数为n,则总的组合数为n * (n - 1)。所以使用2层for循环遍历坐标数组,即固定一个点,计算所有与这个点距离相等的点的个数,用map记录符合条件的点的个数。然后将符合条件的点的组合数累加入结果中。
class Solution { public: int numberOfBoomerangs(vector<pair<int, int>>& points) { int res = 0; for (int i = 0; i != points.size(); i++) { unordered_map<int, int> m; for (int j = 0; j != points.size(); j++) { int a = points[i].first - points[j].first; int b = points[i].second - points[j].second; m[a * a + b * b]++; } for (auto it = m.begin(); it != m.end(); it++) res += (it->second * (it->second - 1)); } return res; } }; // 283 ms
[LeetCode] Number of Boomerangs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。