平台网站如何做推广方案设计,青岛物流网站建设,中铁建设集团有限公司电话号码,免费的微商城Every day a Leetcode
题目来源#xff1a;447. 回旋镖的数量
解法1#xff1a;枚举 哈希
题目所描述的回旋镖可以视作一个 V 型的折线。我们可以枚举每个 points[i]#xff0c;将其当作 V\texttt{V}V 型的拐点。设 points 中有 m 个点到 points[i] 的距离均相等#…Every day a Leetcode
题目来源447. 回旋镖的数量
解法1枚举 哈希
题目所描述的回旋镖可以视作一个 V 型的折线。我们可以枚举每个 points[i]将其当作 V\texttt{V}V 型的拐点。设 points 中有 m 个点到 points[i] 的距离均相等我们需要从这 m 点中选出 2 个点当作回旋镖的 2 个端点由于题目要求考虑元组的顺序因此方案数即为在 m 个元素中选出 2 个不同元素的排列数。 据此我们可以遍历 points计算并统计所有点到 points[i] 的距离将每个距离的出现次数记录在哈希表中然后遍历哈希表并用上述公式计算并累加回旋镖的个数。
在代码实现时我们可以直接保存距离的平方避免复杂的开方运算。
代码
/** lc appleetcode.cn id447 langcpp** [447] 回旋镖的数量*/// lc codestart// 枚举 哈希class Solution
{
public:int numberOfBoomerangs(vectorvectorint points){// 特判if (points.empty())return 0;int ans 0;for (const vectorint p : points){unordered_mapint, int distances;for (const vectorint q : points){int distance (p[0] - q[0]) * (p[0] - q[0]) (p[1] - q[1]) * (p[1] - q[1]);distances[distance];}for (auto [_, dis] : distances)ans dis * (dis - 1);}return ans;}
};
// lc codeend结果 复杂度分析
时间复杂度O(n2)其中 n 是数组 points 的长度。
空间复杂度O(n)其中 n 是数组 points 的长度。
